Submission #499752

#	Time	Username	Problem	Language	Result	Execution time	Memory
499752		jamezzz	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1042 ms	164832 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

#define pf printf
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;

int N=200005;

struct node{
	int s,e,m;
	vector<int> v;
	node *l,*r;
	node(int _s,int _e){
		s=_s;e=_e;m=(s+e)/2;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void up(int x,int nv){
		if(s==x&&e==x){v.pb(nv);return;}
		if(x<=m)l->up(x,nv);
		else r->up(x,nv);
	}
	void init(){
		if(s!=e)l->init(),r->init();
		else{disc(v);return;}
		v.resize(sz(l->v)+sz(r->v));
		merge(all(l->v),all(r->v),v.begin());
	}
	ll qry(int x,int y,int a,int b){
		if(x>y||a>b)return 0;
		if(s==x&&e==y)return upper_bound(all(v),b)-lower_bound(all(v),a);
		if(y<=m)return l->qry(x,y,a,b);
		if(x>m)return r->qry(x,y,a,b);
		return l->qry(x,m,a,b)+r->qry(m+1,y,a,b);
	}
}*vertices,*horizontal,*vertical,*faces;

void addRiver(int r,int c){
	vertices->up(r,c);
	horizontal->up(r,c-1);horizontal->up(r,c);
	vertical->up(r-1,c);vertical->up(r,c);
	faces->up(r-1,c-1);faces->up(r,c-1);faces->up(r-1,c);faces->up(r,c);
}

void init(int R,int C,int sr,int sc,int M,char *S){
	vertices=new node(0,N);
	horizontal=new node(0,N);
	vertical=new node(0,N);
	faces=new node(0,N);
	
	addRiver(sr,sc);
	for(int i=0;i<M;++i){
		if(S[i]=='N')--sr;
		if(S[i]=='S')++sr;
		if(S[i]=='W')--sc;
		if(S[i]=='E')++sc;
		addRiver(sr,sc);
	}
	
	vertices->init();
	horizontal->init();
	vertical->init();
	faces->init();
}

int colour(int t,int l,int b,int r){
	ll h=b-t+1,w=r-l+1;
	ll v=h*w-vertices->qry(t,b,l,r);
	ll e=(w-1)*h-horizontal->qry(t,b,l,r-1)+(h-1)*w-vertical->qry(t,b-1,l,r);
	ll f=(h-1)*(w-1)-faces->qry(t,b-1,l,r-1);
	if(vertices->qry(t+1,b-1,l+1,r-1)==vertices->qry(0,N,0,N))++f;
    return v-e+f;
}

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