oj.uz

Submission #499752

# Submission time Handle Problem Language Result Execution time Memory
499752 2021-12-29T12:01:30 Z jamezzz Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 1042 ms 164832 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

#define pf printf
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;

int N=200005;

struct node{
	int s,e,m;
	vector<int> v;
	node *l,*r;
	node(int _s,int _e){
		s=_s;e=_e;m=(s+e)/2;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void up(int x,int nv){
		if(s==x&&e==x){v.pb(nv);return;}
		if(x<=m)l->up(x,nv);
		else r->up(x,nv);
	}
	void init(){
		if(s!=e)l->init(),r->init();
		else{disc(v);return;}
		v.resize(sz(l->v)+sz(r->v));
		merge(all(l->v),all(r->v),v.begin());
	}
	ll qry(int x,int y,int a,int b){
		if(x>y||a>b)return 0;
		if(s==x&&e==y)return upper_bound(all(v),b)-lower_bound(all(v),a);
		if(y<=m)return l->qry(x,y,a,b);
		if(x>m)return r->qry(x,y,a,b);
		return l->qry(x,m,a,b)+r->qry(m+1,y,a,b);
	}
}*vertices,*horizontal,*vertical,*faces;

void addRiver(int r,int c){
	vertices->up(r,c);
	horizontal->up(r,c-1);horizontal->up(r,c);
	vertical->up(r-1,c);vertical->up(r,c);
	faces->up(r-1,c-1);faces->up(r,c-1);faces->up(r-1,c);faces->up(r,c);
}

void init(int R,int C,int sr,int sc,int M,char *S){
	vertices=new node(0,N);
	horizontal=new node(0,N);
	vertical=new node(0,N);
	faces=new node(0,N);
	
	addRiver(sr,sc);
	for(int i=0;i<M;++i){
		if(S[i]=='N')--sr;
		if(S[i]=='S')++sr;
		if(S[i]=='W')--sc;
		if(S[i]=='E')++sc;
		addRiver(sr,sc);
	}
	
	vertices->init();
	horizontal->init();
	vertical->init();
	faces->init();
}

int colour(int t,int l,int b,int r){
	ll h=b-t+1,w=r-l+1;
	ll v=h*w-vertices->qry(t,b,l,r);
	ll e=(w-1)*h-horizontal->qry(t,b,l,r-1)+(h-1)*w-vertical->qry(t,b-1,l,r);
	ll f=(h-1)*(w-1)-faces->qry(t,b-1,l,r-1);
	if(vertices->qry(t+1,b-1,l+1,r-1)==vertices->qry(0,N,0,N))++f;
    return v-e+f;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 100528 KB Output is correct
2 Correct 86 ms 100932 KB Output is correct
3 Correct 95 ms 100520 KB Output is correct
4 Correct 82 ms 100600 KB Output is correct
5 Correct 80 ms 100992 KB Output is correct
6 Correct 83 ms 100396 KB Output is correct
7 Correct 80 ms 100472 KB Output is correct
8 Correct 86 ms 100432 KB Output is correct
9 Correct 87 ms 100376 KB Output is correct
10 Correct 105 ms 100396 KB Output is correct
11 Correct 93 ms 100640 KB Output is correct
12 Correct 81 ms 100804 KB Output is correct
13 Correct 90 ms 101056 KB Output is correct
14 Correct 83 ms 101364 KB Output is correct
15 Correct 77 ms 100416 KB Output is correct
16 Correct 80 ms 100420 KB Output is correct
17 Correct 79 ms 100372 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 100420 KB Output is correct
2 Correct 79 ms 100372 KB Output is correct
3 Correct 230 ms 131740 KB Output is correct
4 Correct 271 ms 150172 KB Output is correct
5 Correct 266 ms 150164 KB Output is correct
6 Correct 269 ms 140364 KB Output is correct
7 Correct 264 ms 139696 KB Output is correct
8 Correct 225 ms 108332 KB Output is correct
9 Correct 278 ms 150356 KB Output is correct
10 Correct 277 ms 150172 KB Output is correct
11 Correct 259 ms 140312 KB Output is correct
12 Correct 222 ms 147044 KB Output is correct
13 Correct 227 ms 150180 KB Output is correct
14 Correct 214 ms 150060 KB Output is correct
15 Correct 223 ms 140300 KB Output is correct
16 Correct 233 ms 136680 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 100416 KB Output is correct
2 Correct 154 ms 146164 KB Output is correct
3 Correct 206 ms 160844 KB Output is correct
4 Correct 186 ms 151696 KB Output is correct
5 Correct 187 ms 142876 KB Output is correct
6 Correct 148 ms 113588 KB Output is correct
7 Correct 171 ms 120948 KB Output is correct
8 Correct 162 ms 142060 KB Output is correct
9 Correct 167 ms 138324 KB Output is correct
10 Correct 122 ms 111048 KB Output is correct
11 Correct 174 ms 125304 KB Output is correct
12 Correct 151 ms 146196 KB Output is correct
13 Correct 206 ms 161016 KB Output is correct
14 Correct 188 ms 151692 KB Output is correct
15 Correct 175 ms 142808 KB Output is correct
16 Correct 142 ms 111648 KB Output is correct
17 Correct 155 ms 121440 KB Output is correct
18 Correct 184 ms 147156 KB Output is correct
19 Correct 179 ms 153796 KB Output is correct
20 Correct 183 ms 153704 KB Output is correct
21 Correct 164 ms 142044 KB Output is correct
22 Correct 162 ms 138164 KB Output is correct
23 Correct 121 ms 110948 KB Output is correct
24 Correct 177 ms 125392 KB Output is correct
25 Correct 171 ms 146148 KB Output is correct
26 Correct 199 ms 160836 KB Output is correct
27 Correct 186 ms 151752 KB Output is correct
28 Correct 185 ms 142728 KB Output is correct
29 Correct 149 ms 111620 KB Output is correct
30 Correct 164 ms 121364 KB Output is correct
31 Correct 188 ms 147044 KB Output is correct
32 Correct 208 ms 153832 KB Output is correct
33 Correct 195 ms 153796 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 100528 KB Output is correct
2 Correct 86 ms 100932 KB Output is correct
3 Correct 95 ms 100520 KB Output is correct
4 Correct 82 ms 100600 KB Output is correct
5 Correct 80 ms 100992 KB Output is correct
6 Correct 83 ms 100396 KB Output is correct
7 Correct 80 ms 100472 KB Output is correct
8 Correct 86 ms 100432 KB Output is correct
9 Correct 87 ms 100376 KB Output is correct
10 Correct 105 ms 100396 KB Output is correct
11 Correct 93 ms 100640 KB Output is correct
12 Correct 81 ms 100804 KB Output is correct
13 Correct 90 ms 101056 KB Output is correct
14 Correct 83 ms 101364 KB Output is correct
15 Correct 77 ms 100416 KB Output is correct
16 Correct 80 ms 100420 KB Output is correct
17 Correct 79 ms 100372 KB Output is correct
18 Correct 892 ms 130112 KB Output is correct
19 Correct 276 ms 105016 KB Output is correct
20 Correct 295 ms 104028 KB Output is correct
21 Correct 262 ms 104348 KB Output is correct
22 Correct 275 ms 104552 KB Output is correct
23 Correct 248 ms 105020 KB Output is correct
24 Correct 284 ms 104272 KB Output is correct
25 Correct 281 ms 104792 KB Output is correct
26 Correct 281 ms 104636 KB Output is correct
27 Correct 482 ms 125980 KB Output is correct
28 Correct 435 ms 117220 KB Output is correct
29 Correct 446 ms 124764 KB Output is correct
30 Correct 753 ms 150480 KB Output is correct
31 Correct 85 ms 100548 KB Output is correct
32 Correct 651 ms 125840 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 100528 KB Output is correct
2 Correct 86 ms 100932 KB Output is correct
3 Correct 95 ms 100520 KB Output is correct
4 Correct 82 ms 100600 KB Output is correct
5 Correct 80 ms 100992 KB Output is correct
6 Correct 83 ms 100396 KB Output is correct
7 Correct 80 ms 100472 KB Output is correct
8 Correct 86 ms 100432 KB Output is correct
9 Correct 87 ms 100376 KB Output is correct
10 Correct 105 ms 100396 KB Output is correct
11 Correct 93 ms 100640 KB Output is correct
12 Correct 81 ms 100804 KB Output is correct
13 Correct 90 ms 101056 KB Output is correct
14 Correct 83 ms 101364 KB Output is correct
15 Correct 77 ms 100416 KB Output is correct
16 Correct 80 ms 100420 KB Output is correct
17 Correct 79 ms 100372 KB Output is correct
18 Correct 892 ms 130112 KB Output is correct
19 Correct 276 ms 105016 KB Output is correct
20 Correct 295 ms 104028 KB Output is correct
21 Correct 262 ms 104348 KB Output is correct
22 Correct 275 ms 104552 KB Output is correct
23 Correct 248 ms 105020 KB Output is correct
24 Correct 284 ms 104272 KB Output is correct
25 Correct 281 ms 104792 KB Output is correct
26 Correct 281 ms 104636 KB Output is correct
27 Correct 482 ms 125980 KB Output is correct
28 Correct 435 ms 117220 KB Output is correct
29 Correct 446 ms 124764 KB Output is correct
30 Correct 753 ms 150480 KB Output is correct
31 Correct 85 ms 100548 KB Output is correct
32 Correct 651 ms 125840 KB Output is correct
33 Correct 154 ms 146164 KB Output is correct
34 Correct 206 ms 160844 KB Output is correct
35 Correct 186 ms 151696 KB Output is correct
36 Correct 187 ms 142876 KB Output is correct
37 Correct 148 ms 113588 KB Output is correct
38 Correct 171 ms 120948 KB Output is correct
39 Correct 162 ms 142060 KB Output is correct
40 Correct 167 ms 138324 KB Output is correct
41 Correct 122 ms 111048 KB Output is correct
42 Correct 174 ms 125304 KB Output is correct
43 Correct 151 ms 146196 KB Output is correct
44 Correct 206 ms 161016 KB Output is correct
45 Correct 188 ms 151692 KB Output is correct
46 Correct 175 ms 142808 KB Output is correct
47 Correct 142 ms 111648 KB Output is correct
48 Correct 155 ms 121440 KB Output is correct
49 Correct 184 ms 147156 KB Output is correct
50 Correct 179 ms 153796 KB Output is correct
51 Correct 183 ms 153704 KB Output is correct
52 Correct 164 ms 142044 KB Output is correct
53 Correct 162 ms 138164 KB Output is correct
54 Correct 121 ms 110948 KB Output is correct
55 Correct 177 ms 125392 KB Output is correct
56 Correct 171 ms 146148 KB Output is correct
57 Correct 199 ms 160836 KB Output is correct
58 Correct 186 ms 151752 KB Output is correct
59 Correct 185 ms 142728 KB Output is correct
60 Correct 149 ms 111620 KB Output is correct
61 Correct 164 ms 121364 KB Output is correct
62 Correct 188 ms 147044 KB Output is correct
63 Correct 208 ms 153832 KB Output is correct
64 Correct 195 ms 153796 KB Output is correct
65 Correct 230 ms 131740 KB Output is correct
66 Correct 271 ms 150172 KB Output is correct
67 Correct 266 ms 150164 KB Output is correct
68 Correct 269 ms 140364 KB Output is correct
69 Correct 264 ms 139696 KB Output is correct
70 Correct 225 ms 108332 KB Output is correct
71 Correct 278 ms 150356 KB Output is correct
72 Correct 277 ms 150172 KB Output is correct
73 Correct 259 ms 140312 KB Output is correct
74 Correct 222 ms 147044 KB Output is correct
75 Correct 227 ms 150180 KB Output is correct
76 Correct 214 ms 150060 KB Output is correct
77 Correct 223 ms 140300 KB Output is correct
78 Correct 233 ms 136680 KB Output is correct
79 Correct 369 ms 145516 KB Output is correct
80 Correct 415 ms 141692 KB Output is correct
81 Correct 396 ms 114496 KB Output is correct
82 Correct 501 ms 128844 KB Output is correct
83 Correct 800 ms 149772 KB Output is correct
84 Correct 1042 ms 164832 KB Output is correct
85 Correct 857 ms 155540 KB Output is correct
86 Correct 878 ms 146412 KB Output is correct
87 Correct 740 ms 115272 KB Output is correct
88 Correct 745 ms 124984 KB Output is correct
89 Correct 725 ms 150772 KB Output is correct
90 Correct 1000 ms 157356 KB Output is correct
91 Correct 847 ms 157200 KB Output is correct