Submission #4353758


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 C++14 (GCC 5.4.1)
Score 800
Code Size 5090 Byte
Status
Exec Time 678 ms
Memory 16920 KB

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 1 ms 256 KB
02.txt 1 ms 256 KB
11.txt 1 ms 256 KB
12.txt 1 ms 256 KB
13.txt 1 ms 256 KB
14.txt 1 ms 256 KB
15.txt 5 ms 384 KB
16.txt 664 ms 16456 KB
17.txt 658 ms 16460 KB
18.txt 678 ms 16496 KB
19.txt 664 ms 16460 KB
20.txt 664 ms 16460 KB
21.txt 670 ms 16920 KB
22.txt 659 ms 16460 KB
23.txt 662 ms 16468 KB
24.txt 666 ms 16460 KB
25.txt 646 ms 16496 KB