oj.uz

Submission #930458

# Submission time Handle Problem Language Result Execution time Memory
930458 2024-02-19T21:48:53 Z amirhoseinfar1385 Land of the Rainbow Gold (APIO17_rainbow) C++17
36 / 100
 868 ms 1020128 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int kaf=(1<<19);

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<<20)*20];
	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++;
   	}
   	//cout<<"wtf: "<<v<<" "<<c<<" "<<e<<" "<<r<<endl;
   	int res=e-v+1+c-r-1;
   	return res;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 1007280 KB Output is correct
2 Correct 426 ms 1007300 KB Output is correct
3 Incorrect 388 ms 1007172 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 378 ms 1007052 KB Output is correct
2 Correct 374 ms 1007236 KB Output is correct
3 Correct 724 ms 1013676 KB Output is correct
4 Correct 822 ms 1015352 KB Output is correct
5 Correct 860 ms 1015060 KB Output is correct
6 Correct 803 ms 1015056 KB Output is correct
7 Correct 801 ms 1015520 KB Output is correct
8 Correct 601 ms 1015360 KB Output is correct
9 Correct 839 ms 1015188 KB Output is correct
10 Correct 868 ms 1015020 KB Output is correct
11 Correct 782 ms 1015180 KB Output is correct
12 Correct 665 ms 1015224 KB Output is correct
13 Correct 678 ms 1014840 KB Output is correct
14 Correct 664 ms 1014948 KB Output is correct
15 Correct 662 ms 1015352 KB Output is correct
16 Correct 779 ms 1014236 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 1007188 KB Output is correct
2 Correct 508 ms 1011560 KB Output is correct
3 Correct 509 ms 1020004 KB Output is correct
4 Correct 516 ms 1014352 KB Output is correct
5 Correct 481 ms 1015156 KB Output is correct
6 Correct 420 ms 1012808 KB Output is correct
7 Correct 440 ms 1012364 KB Output is correct
8 Correct 529 ms 1012048 KB Output is correct
9 Correct 505 ms 1011920 KB Output is correct
10 Correct 425 ms 1009572 KB Output is correct
11 Correct 462 ms 1012156 KB Output is correct
12 Correct 505 ms 1011628 KB Output is correct
13 Correct 516 ms 1020128 KB Output is correct
14 Correct 508 ms 1014620 KB Output is correct
15 Correct 479 ms 1014964 KB Output is correct
16 Correct 442 ms 1012304 KB Output is correct
17 Correct 434 ms 1012592 KB Output is correct
18 Correct 514 ms 1012224 KB Output is correct
19 Correct 513 ms 1015720 KB Output is correct
20 Correct 510 ms 1015592 KB Output is correct
21 Correct 516 ms 1012088 KB Output is correct
22 Correct 523 ms 1012060 KB Output is correct
23 Correct 426 ms 1009748 KB Output is correct
24 Correct 456 ms 1012136 KB Output is correct
25 Correct 506 ms 1011632 KB Output is correct
26 Correct 505 ms 1019996 KB Output is correct
27 Correct 519 ms 1014460 KB Output is correct
28 Correct 465 ms 1015208 KB Output is correct
29 Correct 395 ms 1012304 KB Output is correct
30 Correct 423 ms 1012728 KB Output is correct
31 Correct 488 ms 1012308 KB Output is correct
32 Correct 523 ms 1015552 KB Output is correct
33 Correct 499 ms 1015484 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 1007280 KB Output is correct
2 Correct 426 ms 1007300 KB Output is correct
3 Incorrect 388 ms 1007172 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 1007280 KB Output is correct
2 Correct 426 ms 1007300 KB Output is correct
3 Incorrect 388 ms 1007172 KB Output isn't correct
4 Halted 0 ms 0 KB -