Submission #4353422


Source Code Expand

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;
}

Submission Info

Submission Time
Task C - Checkered Stamps
User wo01
Language C++14 (GCC 5.4.1)
Score 800
Code Size 3482 Byte
Status
Exec Time 270 ms
Memory 26476 KB

Compile Error

./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);
                                                ^

Test Cases

Set Name Score / Max Score Test Cases
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
Case Name Status Exec Time Memory
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