Submission #64189

#	Time	Username	Problem	Language	Result	Execution time	Memory
64189		jangwonyoung	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1974 ms	282744 KiB

rainbow

#include "rainbow.h"
#include<iostream>
#include<set>
using namespace std;
const int N=2e5+831,TS=2e7+2004;
typedef long long ll;
int n,m;
set<int>v[N],e1[N],e2[N],f[N];
int sum[TS],lc[TS],rc[TS];
int rv[N],re1[N],re2[N],rf[N];//Red Velvet Wendy <3
int sz;
int mass;
void put(int sr,int sc){
	for(int i=0; i<2 ;i++){
		for(int j=0; j<2 ;j++) v[sr+i].insert(sc+j);
		e1[sr].insert(sc+i);
		e2[sr+i].insert(sc);
	}
	f[sr].insert(sc);
}
int ins(int id,int pos,int l,int r){
	if(l==r){
		sz++;
		sum[sz]=sum[id]+1;
		return sz;
	}
	int mid=(l+r)/2;
	if(pos<=mid){
		ins(lc[id],pos,l,mid);
		sz++;
		lc[sz]=sz-1;
		rc[sz]=rc[id];	
	}
	else{
		ins(rc[id],pos,mid+1,r);
		sz++;
		lc[sz]=lc[id];
		rc[sz]=sz-1;	
	}
	sum[sz]=sum[lc[sz]]+sum[rc[sz]];
	return sz;
}
int qr(int id,int l,int r,int ll,int rr){
	if(r<ll || l>rr) return 0;
	if(ll<=l && r<=rr) return sum[id];
	int mid=(l+r)/2;
	return qr(lc[id],l,mid,ll,rr)+qr(rc[id],mid+1,r,ll,rr);
}
int cnt(int id1,int id2,int l,int r){
	return qr(id2,1,m+1,l,r)-qr(id1,1,m+1,l,r);
}
void init(int R, int C, int sr, int sc, int M, char *S){
	n=R,m=C;
	put(sr,sc);
	for(int i=0; i<M ;i++){
		if(S[i]=='N') sr--;
		if(S[i]=='E') sc++;
		if(S[i]=='S') sr++;
		if(S[i]=='W') sc--;
		put(sr,sc);
	}
	rv[0]=re1[0]=re2[0]=rf[0]=1;
	sz=1;
	for(int i=1; i<=n+1 ;i++){
		rv[i]=rv[i-1],re1[i]=re1[i-1],re2[i]=re2[i-1],rf[i]=rf[i-1];
		for(auto it=v[i].begin(); it!=v[i].end() ;++it) rv[i]=ins(rv[i],*it,1,m+1);
		for(auto it=e1[i].begin(); it!=e1[i].end() ;++it) re1[i]=ins(re1[i],*it,1,m+1);
		for(auto it=e2[i].begin(); it!=e2[i].end() ;++it) re2[i]=ins(re2[i],*it,1,m+1);
		for(auto it=f[i].begin(); it!=f[i].end() ;++it) rf[i]=ins(rf[i],*it,1,m+1);
	}
	mass=cnt(rf[0],rf[n],1,m+1);
}
int colour(int ar, int ac, int br, int bc){
	int v=(br-ar+bc-ac)*2+4+cnt(rv[ar],rv[br],ac+1,bc);
	int e=(br-ar+bc-ac)*2+4+cnt(re1[ar-1],re1[br],ac+1,bc)+cnt(re2[ar],re2[br],ac,bc);
	int f=cnt(rf[ar-1],rf[br],ac,bc);
	if(ar+2<=br && ac+2<=bc && cnt(rf[ar],rf[br-1],ac+1,bc-1)==mass){
		return 2+e-v-f;
	}
	return 1+e-v-f;
}

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