Submission #4353112


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n;
vector<P2>query[2][2];
vector<int>zax[2][2],zay[2][2];
struct seg{
	int seg[(1<<20)];
	int v[(1<<20)];
	bool f[(1<<20)];
	void ini(){
		memset(seg,0,sizeof(seg));
		memset(v,0,sizeof(v));
		memset(f,0,sizeof(f));
	}
	void init(int i,int x){
		v[i+(1<<19)-1] = x;
	}
	void make(){
		for(int i=(1<<19)-2;i>=0;i--){
			v[i] = v[i*2+1]+v[i*2+2];
		}
	}
	void lazy(int k){
		seg[k*2+1] = v[k*2+1]-seg[k*2+1];
		seg[k*2+2] = v[k*2+2]-seg[k*2+2];
		f[k*2+1] ^= 1;
		f[k*2+2] ^= 1;
		f[k] = 0;
	}
	int update(int a,int b,int k,int l,int r){
		if(r<a || b<l) return seg[k];
		if(a<=l && r<=b){
			seg[k] = v[k]-seg[k];
			f[k] ^= 1;
			return seg[k];
		}
		if(f[k]) lazy(k);
		return seg[k] = update(a,b,k*2+1,l,(l+r)/2)+update(a,b,k*2+2,(l+r)/2+1,r);
	}
	int get(){ return seg[0]; }
}t;

map<int,vector<P> >M;
vector<int>z;
ll sol(int a,int b){
	t.ini(); z.clear(); M.clear();
//	cout << z.size() << " " << a << " " << b << endl; 
	for(int i=0;i<query[a][b].size();i++){
		z.pb(query[a][b][i].fi.fi-1); z.pb(query[a][b][i].fi.fi);
		z.pb(query[a][b][i].fi.sc); z.pb(query[a][b][i].fi.sc+1);
		M[query[a][b][i].sc.fi].pb(mp(query[a][b][i].fi.fi,query[a][b][i].fi.sc));
		M[query[a][b][i].sc.sc+1].pb(mp(query[a][b][i].fi.fi,query[a][b][i].fi.sc));
	}
	sort(z.begin(),z.end()); z.erase(unique(z.begin(),z.end()),z.end());
	for(int i=0;i<z.size()-1;i++) t.init(i,z[i+1]-z[i]);
	t.make();
	int pre = 0;
	ll ret = 0;
	for(map<int,vector<P> >::iterator it = M.begin();it != M.end();it++){
		vector<P>&v = it->sc;
		ret += 1LL * (it->fi - pre) * t.get(); pre = it->fi;
		for(int i=0;i<v.size();i++){
			int x = v[i].fi;
			int y = v[i].sc;
			x = lower_bound(z.begin(),z.end(),x)-z.begin();
			y = lower_bound(z.begin(),z.end(),y)-z.begin();
			t.update(x,y,0,0,(1<<19)-1);
		}
	}
	return ret;
}
int main(){
	scanf("%d",&n);
	rep(i,n){
		int h,w,r,c; scanf("%d%d%d%d",&r,&c,&h,&w);
		rep(x,2)rep(y,2){
			if((x+y)%2 == (h+w)%2){
			    int hh = h;
			    while(hh%2 != x%2) hh++;
				int A = (hh+1)/2;
				hh = h+r-1;
				while(hh%2 != x%2) hh--;
				int B = (hh+1)/2;
				hh = w;
				while(hh%2 != y%2) hh++;
				int C = (hh+1)/2;
				hh = w+c-1;
				while(hh%2 != y%2) hh--;
				int D = (hh+1)/2;
				if(A<=B && C<=D){
					
					query[x][y].pb(mp(mp(A,B),mp(C,D)));
				//	cout << x << y << A << B << C  << D << endl;
				}
			}
		}
	}
	ll ans = 0;
	rep(x,2)rep(y,2) {if(query[x][y].empty()) continue;ans += sol(x,y);}
	cout << ans << endl;
}

Submission Info

Submission Time
Task C - Checkered Stamps
User IH19980412
Language C++14 (GCC 5.4.1)
Score 800
Code Size 3154 Byte
Status
Exec Time 674 ms
Memory 24412 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:91:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:93:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int h,w,r,c; scanf("%d%d%d%d",&r,&c,&h,&w);
                                             ^

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 9472 KB
02.txt 7 ms 9472 KB
11.txt 5 ms 9472 KB
12.txt 5 ms 9472 KB
13.txt 7 ms 9472 KB
14.txt 7 ms 9472 KB
15.txt 10 ms 9600 KB
16.txt 649 ms 24408 KB
17.txt 669 ms 24348 KB
18.txt 657 ms 24328 KB
19.txt 648 ms 24288 KB
20.txt 646 ms 24328 KB
21.txt 648 ms 24276 KB
22.txt 653 ms 24328 KB
23.txt 649 ms 24284 KB
24.txt 652 ms 24332 KB
25.txt 674 ms 24412 KB