oj.uz

Submission #930937

# Submission time Handle Problem Language Result Execution time Memory
930937 2024-02-20T20:52:41 Z amirhoseinfar1385 Land of the Rainbow Gold (APIO17_rainbow) C++17
36 / 100
 873 ms 1024656 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
long long kaf=(1<<19);

struct segment{
	vector<long long>all[maxn];
	void add(long long r,long long c){
		all[r].push_back(c);
	}	
	struct node{
		long long lc,rc,sum;
		node(){
			lc=rc=sum=0;
		}
	};
	node seg[(1<<20)*10];
	long long root[maxn],rt=0,nx=1;
	void calc(long long i){
		seg[i].sum=seg[seg[i].lc].sum+seg[seg[i].rc].sum;
	}
	long long ins(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return i;
		}
		long long now=nx;
		seg[nx]=seg[i];
		nx++;
		if(l>=tl&&r<=tr){
			seg[nx-1].sum+=w;
			return nx-1;
		}
		long long 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;
	}
	long long get(long long i,long long l,long long r,long long tl,long long tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i].sum;
		}
		long long m=(l+r)>>1;
		return get(seg[i].lc,l,m,tl,tr)+get(seg[i].rc,m+1,r,tl,tr);
	}
	long long pors(long long top,long long bot,long long tr,long long 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(long long 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;
long long mxr=-1,mxc=-1,mnr=maxn+10,mnc=maxn+10;

void add(long long r,long long 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(long long 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();
}

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 1010468 KB Output is correct
2 Correct 352 ms 1010800 KB Output is correct
3 Incorrect 357 ms 1010256 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 347 ms 1010520 KB Output is correct
2 Correct 340 ms 1010360 KB Output is correct
3 Correct 742 ms 1019484 KB Output is correct
4 Correct 829 ms 1021984 KB Output is correct
5 Correct 860 ms 1022140 KB Output is correct
6 Correct 785 ms 1022344 KB Output is correct
7 Correct 849 ms 1023008 KB Output is correct
8 Correct 604 ms 1022400 KB Output is correct
9 Correct 873 ms 1021992 KB Output is correct
10 Correct 867 ms 1022348 KB Output is correct
11 Correct 834 ms 1022356 KB Output is correct
12 Correct 635 ms 1022456 KB Output is correct
13 Correct 661 ms 1021868 KB Output is correct
14 Correct 661 ms 1021860 KB Output is correct
15 Correct 663 ms 1022856 KB Output is correct
16 Correct 786 ms 1020572 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 1010500 KB Output is correct
2 Correct 512 ms 1019036 KB Output is correct
3 Correct 488 ms 1024584 KB Output is correct
4 Correct 478 ms 1020724 KB Output is correct
5 Correct 462 ms 1020336 KB Output is correct
6 Correct 402 ms 1020692 KB Output is correct
7 Correct 416 ms 1020500 KB Output is correct
8 Correct 540 ms 1019560 KB Output is correct
9 Correct 514 ms 1019636 KB Output is correct
10 Correct 388 ms 1014860 KB Output is correct
11 Correct 447 ms 1019428 KB Output is correct
12 Correct 552 ms 1018940 KB Output is correct
13 Correct 478 ms 1024492 KB Output is correct
14 Correct 492 ms 1020880 KB Output is correct
15 Correct 477 ms 1020388 KB Output is correct
16 Correct 395 ms 1019968 KB Output is correct
17 Correct 459 ms 1021172 KB Output is correct
18 Correct 482 ms 1019608 KB Output is correct
19 Correct 500 ms 1021352 KB Output is correct
20 Correct 498 ms 1021356 KB Output is correct
21 Correct 524 ms 1019784 KB Output is correct
22 Correct 509 ms 1019796 KB Output is correct
23 Correct 386 ms 1014836 KB Output is correct
24 Correct 451 ms 1019476 KB Output is correct
25 Correct 521 ms 1019036 KB Output is correct
26 Correct 489 ms 1024656 KB Output is correct
27 Correct 483 ms 1020996 KB Output is correct
28 Correct 476 ms 1020328 KB Output is correct
29 Correct 393 ms 1019884 KB Output is correct
30 Correct 419 ms 1020916 KB Output is correct
31 Correct 490 ms 1019592 KB Output is correct
32 Correct 505 ms 1021156 KB Output is correct
33 Correct 509 ms 1021320 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 1010468 KB Output is correct
2 Correct 352 ms 1010800 KB Output is correct
3 Incorrect 357 ms 1010256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 1010468 KB Output is correct
2 Correct 352 ms 1010800 KB Output is correct
3 Incorrect 357 ms 1010256 KB Output isn't correct
4 Halted 0 ms 0 KB -