Submission #4353755


Source Code Expand

Copy
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;

template<class Handler>
struct segtree_lazy{
	using val_t = typename Handler::val_t;
	using opr_t = typename Handler::opr_t;
	int N;
	vector<val_t> val;
	vector<opr_t> lazy;
	segtree_lazy(){}
	segtree_lazy(int n){init(n);}
	segtree_lazy(const vector<val_t>& vc){init(vc);}
	void init(int n){
		N=1;
		while(N<n) N*=2;
		val .assign(N*2,val_t::e());
		lazy.assign(N*2,opr_t::e());
	}
	void init(const vector<val_t>& vc){
		int n = vc.size();
		N=1;
		while(N<n) N*=2;
		val .assign(N*2,val_t::e());
		rep(i,n) val[i+N] = vc[i];
		for(int i=N-1;i>0;i--) val[i] = val[i*2] + val[i*2+1];
		lazy.assign(N*2,opr_t::e());
	}
	val_t realvalue(int k,int l,int r){
//		return Handler::act(lazy[k],val[k]);
		return Handler::act(lazy[k],val[k],k,l,r);
	}

	val_t query(int a,int b,int l=0,int r=-1,int k=1){	//query_calc
		if(r==-1) r=N;
		if(b<=l||r<=a) return val_t::e();
		if(a<=l&&r<=b) return realvalue(k,l,r);
		propagate(l,r,k);
		val_t ret = query(a,b,l,(l+r)/2,k*2) + query(a,b,(l+r)/2,r,k*2+1);
		val[k] = realvalue(k*2,l,(l+r)/2) + realvalue(k*2+1,(l+r)/2,r);
		return ret;

	}
//	val_t query_leftassoc(){}
	void update(int a,int b,const opr_t &x,int l=0,int r=-1,int k=1){	//query_update
		if(r==-1) r=N;
		if(b<=l||r<=a) return;
		if(a<=l&&r<=b){
			Handler::setg2fg(x,lazy[k]);
			return;
		}
		propagate(l,r,k);
		update(a,b,x,l,(l+r)/2,k*2);
		update(a,b,x,(l+r)/2,r,k*2+1);
		val[k] = realvalue(k*2,l,(l+r)/2) + realvalue(k*2+1,(l+r)/2,r);
	}
	void propagate(int l,int r,int k){	//opr_child -> opr_parent * opr_child		parent after child
		Handler::setg2fg(lazy[k],lazy[k*2  ]);
		Handler::setg2fg(lazy[k],lazy[k*2+1]);
		lazy[k] = opr_t::e();
	}
};

struct handler{
	struct val_t{
		ll x;
		ll s;
		val_t(){*this = e();}
		val_t(ll x,ll s):x(x),s(s){}

		const static val_t e(){
			return val_t(0,0);
		}
		val_t operator+(const val_t &r) const {
			return val_t(x+r.x,s+r.s);
		}
		friend ostream& operator<<(ostream& o,const val_t& d){return o<<d.x;}
	};

	struct opr_t{
		bool x;
		opr_t(){*this = e();}
		opr_t(bool x):x(x){}

		const static opr_t e(){
			return opr_t(false);
		}
		friend ostream& operator<<(ostream& o,const opr_t& d){return o<<d.x;}
	};

	/*
		もしコピーコストとかが気になって,しかも楽に書けるならsetg2fgを直接書く
		そうじゃないなら g = getfg(f,g)
	*/
	static void setg2fg(const opr_t &f, opr_t &g){	//g -> fg		f after g
		if(f.x) g.x = !g.x;
	}
	static val_t act(const opr_t &f, const val_t &v,int k,int l,int r){
		if(f.x) return val_t(v.s-v.x,v.s);
		else return v;
	}
};
using val_t = handler::val_t;
using opr_t = handler::opr_t;

ll H,W;
int Q;
const int MQ = 100000;
vector<ll> wss;

using T = tuple<int,int,int>;
vector<T> events;

ll solve(V<ll> a,V<ll> b,V<ll> c,V<ll> d){
	H = 1e9 / 2;
	W = 1e9 / 2;
	Q = a.size();
	wss.clear();
	events.clear();

	wss.pb(0);wss.pb(W);
	rep(i,Q){
		wss.pb(c[i]);wss.pb(d[i]);
		events.pb(T(a[i],c[i],d[i]));
		events.pb(T(b[i],c[i],d[i]));
	}
	sort(all(wss));wss.erase(unique(wss.begin(),wss.end()),wss.end());
	sort(all(events));
	events.pb(T(H,0,W));

	W = wss.size();
	
	vector<val_t> vc;
	rep(i,W-1){
		int x = wss[i+1]-wss[i];
		vc.pb(val_t(x,x));
	}
	segtree_lazy<handler> seg(vc);

	ll ans = 0;
	ll ph = 0;

	for(T e:events){
		ll h,l,r;
		tie(h,l,r) = e;
		l = lower_bound(all(wss),l) - wss.begin();
		r = lower_bound(all(wss),r) - wss.begin();

		ll dh = h - ph;
		ll wssum = seg.query(0,W).x;
		ans += dh * wssum;

		seg.update(l,r,opr_t(true));

		ph = h;
	}
	return ans;
}

int main(){
	int N;
	cin>>N;
	V<ll> a(N),b(N),c(N),d(N);
	rep(i,N){
		ll H,W,A,B;
		cin>>H>>W>>A>>B;
		A--,B--;
		a[i] = A;
		b[i] = a[i]+H;
		c[i] = B;
		d[i] = c[i]+W;
	}

	ll ans = 1;rep(i,18) ans *= 10;
	rep(tx,2) rep(ty,2){
		V<ll> A,B,C,D;
		rep(i,N){
			if(a[i]%2==tx && c[i]%2==ty){
				A.pb((a[i]-tx)/2);
				B.pb((b[i]+1-tx)/2);
				C.pb((c[i]-ty)/2);
				D.pb((d[i]+1-ty)/2);
			}
			if(a[i]%2==1-tx && c[i]%2==1-ty){
				A.pb((a[i]+1-tx)/2);
				B.pb((b[i]+1-tx)/2);
				C.pb((c[i]+1-ty)/2);
				D.pb((d[i]+1-ty)/2);
			}
		}
		// show(tx);
		// show(ty);
		// show(A);
		// show(B);
		// show(C);
		// show(D);
		ans -= solve(A,B,C,D);
	}
	cout<<ans<<endl;
}

Submission Info

Submission Time
Task C - Checkered Stamps
User sigma425
Language Text (cat)
Score 0
Code Size 5090 Byte
Status
Exec Time 1 ms
Memory 128 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 01.txt, 02.txt
All 0 / 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 1 ms 128 KB
02.txt 1 ms 128 KB
11.txt 1 ms 128 KB
12.txt 1 ms 128 KB
13.txt 1 ms 128 KB
14.txt 1 ms 128 KB
15.txt 1 ms 128 KB
16.txt 1 ms 128 KB
17.txt 1 ms 128 KB
18.txt 1 ms 128 KB
19.txt 1 ms 128 KB
20.txt 1 ms 128 KB
21.txt 1 ms 128 KB
22.txt 1 ms 128 KB
23.txt 1 ms 128 KB
24.txt 1 ms 128 KB
25.txt 1 ms 128 KB