Submission #146271

#	Time	Username	Problem	Language	Result	Execution time	Memory
146271		TadijaSebez	Land of the Rainbow Gold (APIO17_rainbow)	C++11	47 / 100	3034 ms	35540 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
struct pt{ int x,y;pt(){}pt(int a, int b):x(a),y(b){}};
pt operator - (pt a, pt b){ return pt(a.x-b.x,a.y-b.y);}
bool operator < (pt a, pt b){ return mp(a.x,a.y)<mp(b.x,b.y);}
bool operator == (pt a, pt b){ return mp(a.x,a.y)==mp(b.x,b.y);}
vector<pt> v[4];
void Add(pt p)
{
	v[0].pb(p);
	v[1].pb(p);v[1].pb(p-pt(1,0));
	v[2].pb(p);v[2].pb(p-pt(0,1));
	v[3].pb(p);v[3].pb(p-pt(1,0));v[3].pb(p-pt(0,1));v[3].pb(p-pt(1,1));
}
const int N=400050;
void ckmn(int &a, int b){ a=min(a,b);}
void ckmx(int &a, int b){ a=max(a,b);}
int d;
bool comp(pt a, pt b){ return d==0?a<b:mp(a.y,a.x)<mp(b.y,b.x);}
struct KDTree
{
	int ls[N],rs[N],tsz,root,sum[N];
	pt p[N],l[N],r[N];
	KDTree(){}
	void upd_mn(int c, pt f){ ckmn(l[c].x,f.x);ckmn(l[c].y,f.y);}
	void upd_mx(int c, pt f){ ckmx(r[c].x,f.x);ckmx(r[c].y,f.y);}
	void Build(int &c, int d, vector<pt> v)
	{
		if(v.empty()) return;
		c=++tsz;
		::d=d;
		int mid=(v.size()-1)/2;
		nth_element(v.begin(),v.begin()+mid,v.end());
		p[c]=l[c]=r[c]=v[mid];sum[c]=1;
		vector<pt> u(v.begin()+mid+1,v.end());
		v.resize(mid);
		Build(ls[c],d^1,v);
		Build(rs[c],d^1,u);
		if(ls[c]) upd_mn(c,l[ls[c]]),upd_mx(c,r[ls[c]]),sum[c]+=sum[ls[c]];
		if(rs[c]) upd_mn(c,l[rs[c]]),upd_mx(c,r[rs[c]]),sum[c]+=sum[rs[c]];
	}
	void Build(vector<pt> v){ Build(root,0,v);}
	int Get(int c, int d, pt qs, pt qe)
	{
		if(!c) return 0;
		if(qs.x<=l[c].x && qs.y<=l[c].y && qe.x>=r[c].x && qe.y>=r[c].y) return sum[c];
		if(qe.x<l[c].x || qe.y<l[c].y || qs.x>r[c].x || qs.y>r[c].y) return 0;
		int ans=0;
		if(qs.x<=p[c].x && qs.y<=p[c].y && qe.x>=p[c].x && qe.y>=p[c].y) ans++;
		ans+=Get(ls[c],d^1,qs,qe);
		ans+=Get(rs[c],d^1,qs,qe);
		return ans;
	}
	ll Get(int x1, int y1, int x2, int y2)
	{
		if(x2<x1 || y2<y1) return 0;
		pt L(x1,y1),R(x2,y2);
		return (ll)(x2-x1+1)*(y2-y1+1)-Get(root,0,L,R);
	}
} KDT[4];
void Build()
{
	for(int i=0;i<4;i++)
	{
		sort(v[i].begin(),v[i].end());
		v[i].resize(unique(v[i].begin(),v[i].end())-v[i].begin());
		KDT[i].Build(v[i]);
	}
}
pt mn,mx;
void init(int R, int C, int sr, int sc, int M, char *S)
{
	pt pos(sr,sc);
	Add(pos);
	for(int i=0;i<M;i++)
	{
		if(S[i]=='N') pos.x--;
		if(S[i]=='S') pos.x++;
		if(S[i]=='W') pos.y--;
		if(S[i]=='E') pos.y++;
		Add(pos);
	}
	Build();
	mn=KDT[0].l[KDT[0].root];
	mx=KDT[0].r[KDT[0].root];
}
int colour(int x1, int y1, int x2, int y2)
{
	ll ans=KDT[0].Get(x1,y1,x2,y2)-KDT[1].Get(x1,y1,x2-1,y2)-KDT[2].Get(x1,y1,x2,y2-1)+KDT[3].Get(x1,y1,x2-1,y2-1);
	if(x1<mn.x && y1<mn.y && x2>mx.x && y2>mx.y) ans++;
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26