oj.uz

Submission #471430

# Submission time Handle Problem Language Result Execution time Memory
471430 2021-09-09T07:09:13 Z CSQ31 Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 1201 ms 124744 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
int r,c;
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define pb push_back
typedef pair<int,int> pii;
const int MAXN = 2e5;
struct fen{
	vector<vector<int>>bit;
	vector<set<int>>data;
	int r,c;
	fen(){}
	fen(int _r,int _c){
		r = _r;
		c = _c;
		bit.resize(r+1);
		data.resize(r+1);
	}
	
	void add(int x,int y){
		data[x].insert(y);
	}
	int query(int x,int l,int r){
		int res = 0;
		for(int i=x;i;i-=i&(-i)){
			int p = lower_bound(all(bit[i]),l) - bit[i].begin();
			int q = upper_bound(all(bit[i]),r) - bit[i].begin();
			res+=q-p;
		}
		return res;
	}
	int query(int xl,int xr,int yl,int yr){
		if(xl > xr)return 0;
		return query(xr,yl,yr) - query(xl-1,yl,yr);
	}
	
	void build(){
		for(int i=1;i<=r;i++){
			for(int j=i;j<=r;j+=j&(-j)){
				for(int x:data[i])bit[j].pb(x);
			}
		}
		for(int i=1;i<=r;i++)sort(all(bit[i]));
	}
}river,hedge,vedge,vert;
pii mx = {-1e9,-1e9};
pii mn = {1e9,1e9};
void init(int R, int C, int sr, int sc, int M, char *S) {
	r = R;
	c = C;
	river = fen(r,c);
	hedge = fen(r+1,c);
	vedge = fen(r,c+1);
	vert = fen(r+1,c+1);
int x = sr;
	int y = sc;
	river.add(x,y);
	hedge.add(x,y);
	hedge.add(x+1,y);
	vedge.add(x,y);
	vedge.add(x,y+1);
	vert.add(x,y);
	vert.add(x+1,y);
	vert.add(x,y+1);
	vert.add(x+1,y+1);
	mx.fi = max(mx.fi,x);
	mx.se = max(mx.se,y);
	mn.fi = min(mn.fi,x);
	mn.se = min(mn.se,y);
	for(int i=0;i<M;i++){
		char c = S[i];
		if(c =='N')x--;
		if(c =='S')x++;
		if(c =='W')y--;
		if(c =='E')y++;
		river.add(x,y);
		hedge.add(x,y);
		hedge.add(x+1,y);
		vedge.add(x,y);
		vedge.add(x,y+1);
		vert.add(x,y);
		vert.add(x+1,y);
		vert.add(x,y+1);
		vert.add(x+1,y+1);
		mx.fi = max(mx.fi,x);
		mx.se = max(mx.se,y);
		mn.fi = min(mn.fi,x);
		mn.se = min(mn.se,y);
	}
	river.build();
	vert.build();
	hedge.build();
	vedge.build();
}

int colour(int ar, int ac, int br, int bc) {
	int C = (!(mn.fi <= ar || mn.se <= ac || mx.fi >= br || mx.se >= bc)) + 1;
	int A = river.query(ar,br,ac,bc);
	int V = vert.query(ar+1,br,ac+1,bc);
	int E = hedge.query(ar+1,br,ac,bc) + vedge.query(ar,br,ac+1,bc);
	//cout<<E<<" "<<V<<" "<<A<<" "<<C<<'\n';
	int F = 1+C+E-V;
    return F - A - 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 4 ms 588 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Correct 6 ms 716 KB Output is correct
14 Correct 6 ms 844 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 283 ms 20012 KB Output is correct
4 Correct 419 ms 33084 KB Output is correct
5 Correct 447 ms 32728 KB Output is correct
6 Correct 434 ms 25664 KB Output is correct
7 Correct 433 ms 25376 KB Output is correct
8 Correct 67 ms 1020 KB Output is correct
9 Correct 428 ms 33028 KB Output is correct
10 Correct 452 ms 32824 KB Output is correct
11 Correct 437 ms 25772 KB Output is correct
12 Correct 348 ms 30568 KB Output is correct
13 Correct 346 ms 33064 KB Output is correct
14 Correct 364 ms 32788 KB Output is correct
15 Correct 377 ms 25916 KB Output is correct
16 Correct 323 ms 23924 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 908 ms 108400 KB Output is correct
3 Correct 279 ms 115252 KB Output is correct
4 Correct 311 ms 115492 KB Output is correct
5 Correct 337 ms 99412 KB Output is correct
6 Correct 165 ms 67248 KB Output is correct
7 Correct 251 ms 75320 KB Output is correct
8 Correct 272 ms 29792 KB Output is correct
9 Correct 267 ms 27704 KB Output is correct
10 Correct 107 ms 35700 KB Output is correct
11 Correct 179 ms 46528 KB Output is correct
12 Correct 941 ms 108384 KB Output is correct
13 Correct 276 ms 115300 KB Output is correct
14 Correct 311 ms 115440 KB Output is correct
15 Correct 330 ms 99420 KB Output is correct
16 Correct 151 ms 65232 KB Output is correct
17 Correct 267 ms 79032 KB Output is correct
18 Correct 609 ms 124108 KB Output is correct
19 Correct 533 ms 114520 KB Output is correct
20 Correct 614 ms 118044 KB Output is correct
21 Correct 280 ms 29668 KB Output is correct
22 Correct 264 ms 27772 KB Output is correct
23 Correct 104 ms 35824 KB Output is correct
24 Correct 181 ms 46572 KB Output is correct
25 Correct 901 ms 108332 KB Output is correct
26 Correct 276 ms 115292 KB Output is correct
27 Correct 314 ms 115504 KB Output is correct
28 Correct 323 ms 99328 KB Output is correct
29 Correct 154 ms 65224 KB Output is correct
30 Correct 268 ms 79156 KB Output is correct
31 Correct 614 ms 124108 KB Output is correct
32 Correct 546 ms 114436 KB Output is correct
33 Correct 588 ms 118044 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 4 ms 588 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Correct 6 ms 716 KB Output is correct
14 Correct 6 ms 844 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 898 ms 23148 KB Output is correct
19 Correct 256 ms 1860 KB Output is correct
20 Correct 190 ms 1124 KB Output is correct
21 Correct 224 ms 1336 KB Output is correct
22 Correct 239 ms 1624 KB Output is correct
23 Correct 234 ms 1816 KB Output is correct
24 Correct 234 ms 1348 KB Output is correct
25 Correct 245 ms 1520 KB Output is correct
26 Correct 259 ms 1780 KB Output is correct
27 Correct 389 ms 17860 KB Output is correct
28 Correct 332 ms 9752 KB Output is correct
29 Correct 371 ms 16288 KB Output is correct
30 Correct 894 ms 45652 KB Output is correct
31 Correct 3 ms 332 KB Output is correct
32 Correct 604 ms 19248 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 4 ms 588 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Correct 6 ms 716 KB Output is correct
14 Correct 6 ms 844 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 898 ms 23148 KB Output is correct
19 Correct 256 ms 1860 KB Output is correct
20 Correct 190 ms 1124 KB Output is correct
21 Correct 224 ms 1336 KB Output is correct
22 Correct 239 ms 1624 KB Output is correct
23 Correct 234 ms 1816 KB Output is correct
24 Correct 234 ms 1348 KB Output is correct
25 Correct 245 ms 1520 KB Output is correct
26 Correct 259 ms 1780 KB Output is correct
27 Correct 389 ms 17860 KB Output is correct
28 Correct 332 ms 9752 KB Output is correct
29 Correct 371 ms 16288 KB Output is correct
30 Correct 894 ms 45652 KB Output is correct
31 Correct 3 ms 332 KB Output is correct
32 Correct 604 ms 19248 KB Output is correct
33 Correct 908 ms 108400 KB Output is correct
34 Correct 279 ms 115252 KB Output is correct
35 Correct 311 ms 115492 KB Output is correct
36 Correct 337 ms 99412 KB Output is correct
37 Correct 165 ms 67248 KB Output is correct
38 Correct 251 ms 75320 KB Output is correct
39 Correct 272 ms 29792 KB Output is correct
40 Correct 267 ms 27704 KB Output is correct
41 Correct 107 ms 35700 KB Output is correct
42 Correct 179 ms 46528 KB Output is correct
43 Correct 941 ms 108384 KB Output is correct
44 Correct 276 ms 115300 KB Output is correct
45 Correct 311 ms 115440 KB Output is correct
46 Correct 330 ms 99420 KB Output is correct
47 Correct 151 ms 65232 KB Output is correct
48 Correct 267 ms 79032 KB Output is correct
49 Correct 609 ms 124108 KB Output is correct
50 Correct 533 ms 114520 KB Output is correct
51 Correct 614 ms 118044 KB Output is correct
52 Correct 280 ms 29668 KB Output is correct
53 Correct 264 ms 27772 KB Output is correct
54 Correct 104 ms 35824 KB Output is correct
55 Correct 181 ms 46572 KB Output is correct
56 Correct 901 ms 108332 KB Output is correct
57 Correct 276 ms 115292 KB Output is correct
58 Correct 314 ms 115504 KB Output is correct
59 Correct 323 ms 99328 KB Output is correct
60 Correct 154 ms 65224 KB Output is correct
61 Correct 268 ms 79156 KB Output is correct
62 Correct 614 ms 124108 KB Output is correct
63 Correct 546 ms 114436 KB Output is correct
64 Correct 588 ms 118044 KB Output is correct
65 Correct 283 ms 20012 KB Output is correct
66 Correct 419 ms 33084 KB Output is correct
67 Correct 447 ms 32728 KB Output is correct
68 Correct 434 ms 25664 KB Output is correct
69 Correct 433 ms 25376 KB Output is correct
70 Correct 67 ms 1020 KB Output is correct
71 Correct 428 ms 33028 KB Output is correct
72 Correct 452 ms 32824 KB Output is correct
73 Correct 437 ms 25772 KB Output is correct
74 Correct 348 ms 30568 KB Output is correct
75 Correct 346 ms 33064 KB Output is correct
76 Correct 364 ms 32788 KB Output is correct
77 Correct 377 ms 25916 KB Output is correct
78 Correct 323 ms 23924 KB Output is correct
79 Correct 604 ms 30472 KB Output is correct
80 Correct 652 ms 28436 KB Output is correct
81 Correct 361 ms 36420 KB Output is correct
82 Correct 452 ms 47264 KB Output is correct
83 Correct 1201 ms 108972 KB Output is correct
84 Correct 848 ms 116000 KB Output is correct
85 Correct 671 ms 116140 KB Output is correct
86 Correct 697 ms 100084 KB Output is correct
87 Correct 318 ms 65860 KB Output is correct
88 Correct 460 ms 79724 KB Output is correct
89 Correct 842 ms 124744 KB Output is correct
90 Correct 1050 ms 115368 KB Output is correct
91 Correct 922 ms 118676 KB Output is correct