oj.uz

Submission #64186

# Submission time Handle Problem Language Result Execution time Memory
64186 2018-08-03T12:55:34 Z jangwonyoung Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1357 ms 242212 KB 
#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;
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);
	}	
}
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);
	return 1+e-v-f;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 38264 KB Output is correct
2 Correct 39 ms 38800 KB Output is correct
3 Incorrect 44 ms 38800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 38800 KB Output is correct
2 Correct 39 ms 38800 KB Output is correct
3 Correct 1008 ms 137424 KB Output is correct
4 Correct 1167 ms 204768 KB Output is correct
5 Correct 1166 ms 206524 KB Output is correct
6 Correct 997 ms 206524 KB Output is correct
7 Correct 1256 ms 206524 KB Output is correct
8 Correct 398 ms 206524 KB Output is correct
9 Correct 1226 ms 219404 KB Output is correct
10 Correct 1357 ms 220952 KB Output is correct
11 Correct 1278 ms 220952 KB Output is correct
12 Correct 799 ms 220952 KB Output is correct
13 Correct 740 ms 230768 KB Output is correct
14 Correct 891 ms 232436 KB Output is correct
15 Correct 799 ms 232436 KB Output is correct
16 Correct 1028 ms 232436 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 232436 KB Output is correct
2 Correct 668 ms 242064 KB Output is correct
3 Correct 288 ms 242064 KB Output is correct
4 Correct 338 ms 242212 KB Output is correct
5 Correct 345 ms 242212 KB Output is correct
6 Correct 173 ms 242212 KB Output is correct
7 Incorrect 280 ms 242212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 38264 KB Output is correct
2 Correct 39 ms 38800 KB Output is correct
3 Incorrect 44 ms 38800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 38264 KB Output is correct
2 Correct 39 ms 38800 KB Output is correct
3 Incorrect 44 ms 38800 KB Output isn't correct
4 Halted 0 ms 0 KB -