oj.uz

Submission #930938

# Submission time Handle Problem Language Result Execution time Memory
930938 2024-02-20T20:54:27 Z amirhoseinfar1385 Land of the Rainbow Gold (APIO17_rainbow) C++17
36 / 100
 625 ms 404316 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int kaf=(1<<18);

struct segment{
	vector<int>all[maxn];
	void add(int r,int c){
		all[r].push_back(c);
	}	
	struct node{
		int lc,rc,sum;
		node(){
			lc=rc=sum=0;
		}
	};
	node seg[(1<<19)*15];
	int root[maxn],rt=0,nx=1;
	void calc(int i){
		seg[i].sum=seg[seg[i].lc].sum+seg[seg[i].rc].sum;
	}
	int ins(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return i;
		}
		int now=nx;
		seg[nx]=seg[i];
		nx++;
		if(l>=tl&&r<=tr){
			seg[nx-1].sum+=w;
			return nx-1;
		}
		int m=(l+r)>>1;
		seg[now].lc=ins(seg[now].lc,l,m,tl,tr,w);
		seg[now].rc=ins(seg[now].rc,m+1,r,tl,tr,w);
		calc(now);
		return now;
	}
	int get(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i].sum;
		}
		int m=(l+r)>>1;
		return get(seg[i].lc,l,m,tl,tr)+get(seg[i].rc,m+1,r,tl,tr);
	}
	int pors(int top,int bot,int tr,int tl){
		//cout<<"get: "<<get(root[top],0,kaf-1,tl,tr)<<" hehe "<<get(root[bot-1],0,kaf-1,tl,tr)<<endl;	
		return get(root[top],0,kaf-1,tl,tr)-get(root[bot-1],0,kaf-1,tl,tr);
	}
	void build(){
		for(int i=0;i<maxn;i++){
			sort(all[i].begin(),all[i].end());
			all[i].resize(unique(all[i].begin(),all[i].end())-all[i].begin());
			for(auto x:all[i]){
				rt=ins(rt,0,kaf-1,x,x,1);
			}
			root[i]=rt;
		}
	}
}segv,segeo,segea,segr;
int mxr=-1,mxc=-1,mnr=maxn+10,mnc=maxn+10;

void add(int r,int c){
	//cout<<"addy: "<<r<<" "<<c<<endl;
	mnr=min(mnr,r);
	mxr=max(mxr,r);
	mnc=min(mnc,c);
	mxc=min(mnc,c);
	segv.add(r,c);
	segv.add(r,c+1);
	segv.add(r+1,c);
	segv.add(r+1,c+1);
	segeo.add(r,c);
	segeo.add(r+1,c);
	segea.add(r,c);
	segea.add(r,c+1);
	segr.add(r,c);
}

void build(){
	segv.build();
	segeo.build();
	segea.build();
	segr.build();
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	add(sr,sc);
	for(int i=0;i<M;i++){
		if(S[i]=='N'){
			sr--;
		}
		else if(S[i]=='S'){
			sr++;
		}else if(S[i]=='E'){
			sc++;
		}else{
			sc--;
		}
		add(sr,sc);
	}
	build();
}

int colour(int ar, int ac, int br, int bc) {
   	int v=segv.pors(br,ar+1,bc,ac+1)+(br-ar+2)*2+(bc-ac)*2;
   	int c=1;
   	int e=segeo.pors(br,ar+1,bc,ac)+segea.pors(br,ar,bc,ac+1)+(br-ar+1)*2+(bc-ac+1)*2;
   	int r=segr.pors(br,ar,bc,ac);
   	if(mnr>ar&&mxr<br&&mnc>ac&&mxc<bc){
   		c++;
   	}
   	int res=e-v+1+c-r-1;
   	return res;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 391528 KB Output is correct
2 Correct 138 ms 391664 KB Output is correct
3 Incorrect 146 ms 391644 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 139 ms 391592 KB Output is correct
2 Correct 136 ms 391508 KB Output is correct
3 Correct 469 ms 397248 KB Output is correct
4 Correct 576 ms 399120 KB Output is correct
5 Correct 580 ms 398296 KB Output is correct
6 Correct 514 ms 398452 KB Output is correct
7 Correct 577 ms 398820 KB Output is correct
8 Correct 348 ms 398648 KB Output is correct
9 Correct 625 ms 398392 KB Output is correct
10 Correct 563 ms 398344 KB Output is correct
11 Correct 528 ms 398516 KB Output is correct
12 Correct 396 ms 398516 KB Output is correct
13 Correct 423 ms 398260 KB Output is correct
14 Correct 401 ms 398208 KB Output is correct
15 Correct 381 ms 397364 KB Output is correct
16 Correct 528 ms 395636 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 391504 KB Output is correct
2 Correct 259 ms 395944 KB Output is correct
3 Correct 248 ms 404204 KB Output is correct
4 Correct 257 ms 398596 KB Output is correct
5 Correct 230 ms 399548 KB Output is correct
6 Correct 171 ms 396896 KB Output is correct
7 Correct 184 ms 396628 KB Output is correct
8 Correct 258 ms 396220 KB Output is correct
9 Correct 246 ms 396400 KB Output is correct
10 Correct 161 ms 393872 KB Output is correct
11 Correct 206 ms 396216 KB Output is correct
12 Correct 266 ms 396092 KB Output is correct
13 Correct 248 ms 404316 KB Output is correct
14 Correct 250 ms 398620 KB Output is correct
15 Correct 228 ms 399292 KB Output is correct
16 Correct 162 ms 396600 KB Output is correct
17 Correct 188 ms 396972 KB Output is correct
18 Correct 248 ms 396368 KB Output is correct
19 Correct 256 ms 399804 KB Output is correct
20 Correct 253 ms 399800 KB Output is correct
21 Correct 256 ms 396248 KB Output is correct
22 Correct 259 ms 396232 KB Output is correct
23 Correct 161 ms 393924 KB Output is correct
24 Correct 207 ms 396200 KB Output is correct
25 Correct 261 ms 396284 KB Output is correct
26 Correct 247 ms 404300 KB Output is correct
27 Correct 246 ms 398696 KB Output is correct
28 Correct 227 ms 399292 KB Output is correct
29 Correct 161 ms 396572 KB Output is correct
30 Correct 195 ms 397140 KB Output is correct
31 Correct 256 ms 396368 KB Output is correct
32 Correct 252 ms 399664 KB Output is correct
33 Correct 261 ms 399900 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 391528 KB Output is correct
2 Correct 138 ms 391664 KB Output is correct
3 Incorrect 146 ms 391644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 391528 KB Output is correct
2 Correct 138 ms 391664 KB Output is correct
3 Incorrect 146 ms 391644 KB Output isn't correct
4 Halted 0 ms 0 KB -