提出 #4353422


ソースコード 拡げる

Copy
#include<bits/stdc++.h>

using namespace std;

int countE(int r){
	return r / 2 + 1;
}

int countE(int l, int r){
	return countE(r) - countE(l - 1);
}

struct Segtree{
	struct Node{
		bool flip;
		long long e0, o0; // for even row, even time/odd time
		long long e1, o1;
		Node(){
			flip = false;
			e0 = 0;
			o0 = 0;
			e1 = 0;
			o1 = 0;
		}
	};
	Node mergeNode(Node &n1, Node &n2, int id = -1){
		Node n;
		n.e0 = n1.e0 + n2.e0;
		n.e1 = n1.e1 + n2.e1;
		n.o0 = n1.o0 + n2.o0;
		n.o1 = n1.o1 + n2.o1;
		return n;
	}
	int N;
	Node ns[524288];
	void init(vector<int> vals){
		int N_ = vals.size();
		N = 1;
		while(N < N_) N *= 2;
		for(int i = 0; i < N_ - 1; ++i){
			ns[i + N].e0 = countE(vals[i], vals[i + 1] - 1);
			ns[i + N].o0 = 0;
			ns[i + N].e1 = vals[i + 1] - vals[i] - ns[i + N].e0;
			ns[i + N].o1 = 0;
		}
		for(int i = N_ - 1; i < N; ++i){
			ns[i + N] = Node();
		}
		for(int i = N - 1; i >= 1; --i){
//			printf("init---\n");
			ns[i] = mergeNode(ns[i * 2], ns[i * 2 + 1], i);
		}
	}
	long long count(int prv, int cur){
		if(prv == cur) return 0;
		propagate(1);
		long long e = ns[1].o0;
		long long o = ns[1].o1;
		int numE = countE(prv, cur - 1);
		int numO = cur - prv - numE;
//		printf("count%d %d %lld %lld %d %d\n", prv, cur, e, o, numE, numO);
		return e * numE + o * numO;
	}
	void flipSub(int id){
		ns[id].flip = !ns[id].flip;
		swap(ns[id].e0, ns[id].o0);
		swap(ns[id].e1, ns[id].o1);
	}
	void propagate(int id){
		if(ns[id].flip){
			flipSub(id * 2);
			flipSub(id * 2 + 1);
			ns[id].flip = false;
		}
	}
	void flip(int l, int r, int k, int a, int b){
		if(l <= a && b <= r){
			ns[k].flip = !ns[k].flip;
			swap(ns[k].e0, ns[k].o0);
			swap(ns[k].e1, ns[k].o1);
			return;
		}
		if(r <= a || b <= l){
			return;
		}
		propagate(k);
		flip(l, r, k * 2, a, (a + b) / 2);
		flip(l, r, k * 2 + 1, (a + b) / 2, b);
		ns[k] = mergeNode(ns[k * 2], ns[k * 2 + 1]);
	}
	void flip(int l, int r){
//		printf("flip %d %d\n", l, r);
		flip(l, r, 1, 0, N);
	}
};

Segtree seg;

struct Query{
	int l, r;
	int t;
	Query(){}
	Query(int l, int r, int t):l(l), r(r), t(t){}
};

bool cmp(const Query &q1, const Query &q2){
	return q1.t < q2.t;
}

vector<Query> qs[2];

int N;
int H[100100];
int W[100100];
int R[100100];
int C[100100];

void input(){
	scanf("%d", &N);
	for(int i = 0; i < N; ++i){
		scanf("%d%d%d%d", H + i, W + i, R + i, C + i);
	}
}

vector<int> vals;

int getId(int x){
	return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
}

long long solve(){
	for(int i = 0; i < N; ++i){
		int id = (R[i] + C[i]) % 2;
		qs[id].push_back(Query(C[i], C[i] + W[i], R[i] + id));
		qs[id].push_back(Query(C[i], C[i] + W[i], R[i] + H[i] + id));
	}
	long long ans = 0;
	for(int i = 0; i < 2; ++i){
//		printf("---\n");
		sort(qs[i].begin(), qs[i].end(), cmp);
		vals.clear();
		for(Query q : qs[i]){
			vals.push_back(q.l);
			vals.push_back(q.r);
		}
		sort(vals.begin(), vals.end());
		vals.erase(unique(vals.begin(), vals.end()), vals.end());
		seg.init(vals);
		int prv = 0;
		for(Query q : qs[i]){
//			printf("count %d %d %lld\n", prv, q.t, seg.count(prv, q.t));
			ans += seg.count(prv, q.t);
			prv = q.t;
			int l = getId(q.l);
			int r = getId(q.r);
			seg.flip(l, r);
		}
	}
	return ans;
}

int main(){
	input();
	long long ans = solve();
	printf("%lld\n", ans);
	return 0;
}

提出情報

提出日時
問題 C - Checkered Stamps
ユーザ wo01
言語 C++14 (GCC 5.4.1)
得点 800
コード長 3482 Byte
結果
実行時間 270 ms
メモリ 26476 KB

コンパイルエラー

./Main.cpp: In function ‘void input()’:
./Main.cpp:119:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:121:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", H + i, W + i, R + i, C + i);
                                                ^

ジャッジ結果

セット名 得点 / 配点 テストケース
Sample 0 / 0 01.txt, 02.txt
All 800 / 800 01.txt, 02.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt
ケース名 結果 実行時間 メモリ
01.txt 7 ms 20736 KB
02.txt 7 ms 20736 KB
11.txt 7 ms 20736 KB
12.txt 7 ms 20736 KB
13.txt 7 ms 20736 KB
14.txt 7 ms 20736 KB
15.txt 8 ms 20736 KB
16.txt 269 ms 26404 KB
17.txt 269 ms 26376 KB
18.txt 268 ms 26472 KB
19.txt 266 ms 26412 KB
20.txt 270 ms 26472 KB
21.txt 266 ms 26472 KB
22.txt 266 ms 26476 KB
23.txt 266 ms 26460 KB
24.txt 266 ms 26472 KB
25.txt 267 ms 26464 KB