oj.uz

Submission #105420

# Submission time Handle Problem Language Result Execution time Memory
105420 2019-04-12T06:45:41 Z puyu_liao Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 1558 ms 91144 KB 
#include<bits/stdc++.h>
#include<stdint.h>
using namespace std;
#define IOS {cin.tie(0);ios_base::sync_with_stdio(false);}
#define N 200005
#define lowbit(x) (x&-x)
#include"rainbow.h"
struct dbit{
	vector<int> v[N];
	int n,m;
	void init(int _n,int _m){
		n = _n,m = _m;
		for(int i=1;i<=n;i++) v[i].clear();
	}
	void ins(int x,int y){
		for(;x<=n;x+=lowbit(x)) v[x].push_back(y);
	}
	void preprocess(){
		for(int i=1;i<=n;i++){
			sort(v[i].begin(),v[i].end());
		}
	}
	int qur(int x,int y,int xx,int yy){
		if(x > xx || y > yy) return 0;
		int r = 0;
		for(;x;x-=lowbit(x)) r -= (int)(upper_bound(v[x].begin(),v[x].end(),yy) - lower_bound(v[x].begin(),v[x].end(),y));
		for(;xx;xx-=lowbit(xx)) r += (int)(upper_bound(v[xx].begin(),v[xx].end(),yy) - lower_bound(v[xx].begin(),v[xx].end(),y));
		return r;
	}
}bv,be1,be2,bf;
vector<pair<int,int> > v;
set<pair<int,int> > sv,se1,se2,sf;
int xmn,xmx,ymn,ymx;
 
void put(int sr,int sc){
	sv.insert({sr,sc});
	sv.insert({sr+1,sc});
	sv.insert({sr,sc+1});
	sv.insert({sr+1,sc+1});
	se1.insert({sr,sc}); 
	se1.insert({sr,sc+1}); 
	se2.insert({sr,sc}); 
	se2.insert({sr+1,sc}); 
	sf.insert({sr,sc});
}
 
void init(int R,int C,int sr,int sc,int M,char* S){
	bv.init(R+2,C+2);
	be1.init(R+2,C+2); //vert
	be2.init(R+2,C+2); //hori
	bf.init(R+2,C+2);
	sv.clear();
	se1.clear();
	se2.clear();
	sf.clear();
	put(sr,sc);
	xmn = xmx = sr, ymn = ymx = sc;
	for(int j=0;j<M;j++){
		char &i = S[j];
		if(i == 'N') sr--;
		else if(i == 'E') sc++;
		else if(i == 'W') sc--;
		else if(i == 'S') sr++;
		v.push_back({sr,sc});
		xmx = max(xmx,sr);
		xmn = min(xmn,sr);
		ymx = max(ymx,sc);
		ymn = min(ymn,sc);
		put(sr,sc);
	}
	for(auto i : sv) bv.ins(i.first,i.second);
	for(auto i : se1) be1.ins(i.first,i.second);
	for(auto i : se2) be2.ins(i.first,i.second);
	for(auto i : sf) bf.ins(i.first,i.second);
	bv.preprocess();
	be1.preprocess();
	be2.preprocess();
	bf.preprocess();
}
 
int colour(int ar,int ac,int br,int bc){
	int v = (br-ar+bc-ac+2)*2 + bv.qur(ar,ac+1,br,bc);
	int e = (br-ar+bc-ac+2)*2 + be1.qur(ar-1,ac+1,br,bc) + be2.qur(ar,ac,br,bc);
	int f = bf.qur(ar-1,ac,br,bc);
	//cout << v << ' ' << e << ' ' << f << '\n';
	return e-v-f + 1 + (ar < xmn && ac < ymn && br > xmx && bc > ymx);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19200 KB Output is correct
2 Correct 26 ms 19576 KB Output is correct
3 Correct 21 ms 19200 KB Output is correct
4 Correct 23 ms 19200 KB Output is correct
5 Correct 27 ms 19580 KB Output is correct
6 Correct 21 ms 19200 KB Output is correct
7 Correct 28 ms 19100 KB Output is correct
8 Correct 21 ms 19072 KB Output is correct
9 Correct 21 ms 19200 KB Output is correct
10 Correct 22 ms 19200 KB Output is correct
11 Correct 27 ms 19328 KB Output is correct
12 Correct 25 ms 19456 KB Output is correct
13 Correct 27 ms 19704 KB Output is correct
14 Correct 30 ms 19840 KB Output is correct
15 Correct 21 ms 19072 KB Output is correct
16 Correct 18 ms 19072 KB Output is correct
17 Correct 22 ms 19200 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19072 KB Output is correct
2 Correct 22 ms 19200 KB Output is correct
3 Correct 469 ms 40876 KB Output is correct
4 Correct 693 ms 55432 KB Output is correct
5 Correct 684 ms 55244 KB Output is correct
6 Correct 537 ms 47736 KB Output is correct
7 Correct 730 ms 47336 KB Output is correct
8 Correct 112 ms 20816 KB Output is correct
9 Correct 692 ms 55472 KB Output is correct
10 Correct 644 ms 55108 KB Output is correct
11 Correct 532 ms 47744 KB Output is correct
12 Correct 554 ms 53144 KB Output is correct
13 Correct 472 ms 55424 KB Output is correct
14 Correct 460 ms 55376 KB Output is correct
15 Correct 440 ms 47900 KB Output is correct
16 Correct 546 ms 45516 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19072 KB Output is correct
2 Correct 749 ms 74508 KB Output is correct
3 Correct 558 ms 78692 KB Output is correct
4 Correct 556 ms 78444 KB Output is correct
5 Correct 457 ms 62956 KB Output is correct
6 Correct 178 ms 30576 KB Output is correct
7 Correct 340 ms 38636 KB Output is correct
8 Correct 383 ms 52588 KB Output is correct
9 Correct 377 ms 48628 KB Output is correct
10 Correct 163 ms 26920 KB Output is correct
11 Correct 356 ms 38304 KB Output is correct
12 Correct 779 ms 74568 KB Output is correct
13 Correct 588 ms 78752 KB Output is correct
14 Correct 584 ms 78548 KB Output is correct
15 Correct 460 ms 63076 KB Output is correct
16 Correct 176 ms 28780 KB Output is correct
17 Correct 377 ms 42348 KB Output is correct
18 Correct 713 ms 87404 KB Output is correct
19 Correct 642 ms 77808 KB Output is correct
20 Correct 720 ms 81280 KB Output is correct
21 Correct 425 ms 52584 KB Output is correct
22 Correct 435 ms 48620 KB Output is correct
23 Correct 154 ms 26800 KB Output is correct
24 Correct 328 ms 38416 KB Output is correct
25 Correct 762 ms 74692 KB Output is correct
26 Correct 597 ms 78700 KB Output is correct
27 Correct 596 ms 78504 KB Output is correct
28 Correct 496 ms 63048 KB Output is correct
29 Correct 157 ms 28780 KB Output is correct
30 Correct 311 ms 42432 KB Output is correct
31 Correct 730 ms 87372 KB Output is correct
32 Correct 682 ms 78020 KB Output is correct
33 Correct 652 ms 81080 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19200 KB Output is correct
2 Correct 26 ms 19576 KB Output is correct
3 Correct 21 ms 19200 KB Output is correct
4 Correct 23 ms 19200 KB Output is correct
5 Correct 27 ms 19580 KB Output is correct
6 Correct 21 ms 19200 KB Output is correct
7 Correct 28 ms 19100 KB Output is correct
8 Correct 21 ms 19072 KB Output is correct
9 Correct 21 ms 19200 KB Output is correct
10 Correct 22 ms 19200 KB Output is correct
11 Correct 27 ms 19328 KB Output is correct
12 Correct 25 ms 19456 KB Output is correct
13 Correct 27 ms 19704 KB Output is correct
14 Correct 30 ms 19840 KB Output is correct
15 Correct 21 ms 19072 KB Output is correct
16 Correct 18 ms 19072 KB Output is correct
17 Correct 22 ms 19200 KB Output is correct
18 Correct 1558 ms 45616 KB Output is correct
19 Correct 285 ms 23516 KB Output is correct
20 Correct 296 ms 22736 KB Output is correct
21 Correct 290 ms 23036 KB Output is correct
22 Correct 308 ms 23160 KB Output is correct
23 Correct 270 ms 23576 KB Output is correct
24 Correct 284 ms 22904 KB Output is correct
25 Correct 261 ms 23160 KB Output is correct
26 Correct 338 ms 23392 KB Output is correct
27 Correct 693 ms 40168 KB Output is correct
28 Correct 567 ms 32080 KB Output is correct
29 Correct 636 ms 38672 KB Output is correct
30 Correct 1227 ms 67728 KB Output is correct
31 Correct 24 ms 19328 KB Output is correct
32 Correct 1087 ms 41584 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19200 KB Output is correct
2 Correct 26 ms 19576 KB Output is correct
3 Correct 21 ms 19200 KB Output is correct
4 Correct 23 ms 19200 KB Output is correct
5 Correct 27 ms 19580 KB Output is correct
6 Correct 21 ms 19200 KB Output is correct
7 Correct 28 ms 19100 KB Output is correct
8 Correct 21 ms 19072 KB Output is correct
9 Correct 21 ms 19200 KB Output is correct
10 Correct 22 ms 19200 KB Output is correct
11 Correct 27 ms 19328 KB Output is correct
12 Correct 25 ms 19456 KB Output is correct
13 Correct 27 ms 19704 KB Output is correct
14 Correct 30 ms 19840 KB Output is correct
15 Correct 21 ms 19072 KB Output is correct
16 Correct 18 ms 19072 KB Output is correct
17 Correct 22 ms 19200 KB Output is correct
18 Correct 1558 ms 45616 KB Output is correct
19 Correct 285 ms 23516 KB Output is correct
20 Correct 296 ms 22736 KB Output is correct
21 Correct 290 ms 23036 KB Output is correct
22 Correct 308 ms 23160 KB Output is correct
23 Correct 270 ms 23576 KB Output is correct
24 Correct 284 ms 22904 KB Output is correct
25 Correct 261 ms 23160 KB Output is correct
26 Correct 338 ms 23392 KB Output is correct
27 Correct 693 ms 40168 KB Output is correct
28 Correct 567 ms 32080 KB Output is correct
29 Correct 636 ms 38672 KB Output is correct
30 Correct 1227 ms 67728 KB Output is correct
31 Correct 24 ms 19328 KB Output is correct
32 Correct 1087 ms 41584 KB Output is correct
33 Correct 749 ms 74508 KB Output is correct
34 Correct 558 ms 78692 KB Output is correct
35 Correct 556 ms 78444 KB Output is correct
36 Correct 457 ms 62956 KB Output is correct
37 Correct 178 ms 30576 KB Output is correct
38 Correct 340 ms 38636 KB Output is correct
39 Correct 383 ms 52588 KB Output is correct
40 Correct 377 ms 48628 KB Output is correct
41 Correct 163 ms 26920 KB Output is correct
42 Correct 356 ms 38304 KB Output is correct
43 Correct 779 ms 74568 KB Output is correct
44 Correct 588 ms 78752 KB Output is correct
45 Correct 584 ms 78548 KB Output is correct
46 Correct 460 ms 63076 KB Output is correct
47 Correct 176 ms 28780 KB Output is correct
48 Correct 377 ms 42348 KB Output is correct
49 Correct 713 ms 87404 KB Output is correct
50 Correct 642 ms 77808 KB Output is correct
51 Correct 720 ms 81280 KB Output is correct
52 Correct 425 ms 52584 KB Output is correct
53 Correct 435 ms 48620 KB Output is correct
54 Correct 154 ms 26800 KB Output is correct
55 Correct 328 ms 38416 KB Output is correct
56 Correct 762 ms 74692 KB Output is correct
57 Correct 597 ms 78700 KB Output is correct
58 Correct 596 ms 78504 KB Output is correct
59 Correct 496 ms 63048 KB Output is correct
60 Correct 157 ms 28780 KB Output is correct
61 Correct 311 ms 42432 KB Output is correct
62 Correct 730 ms 87372 KB Output is correct
63 Correct 682 ms 78020 KB Output is correct
64 Correct 652 ms 81080 KB Output is correct
65 Correct 841 ms 56088 KB Output is correct
66 Correct 1010 ms 52088 KB Output is correct
67 Correct 493 ms 30576 KB Output is correct
68 Correct 729 ms 41828 KB Output is correct
69 Correct 1066 ms 78348 KB Output is correct
70 Correct 1339 ms 82284 KB Output is correct
71 Correct 1138 ms 82256 KB Output is correct
72 Correct 922 ms 66656 KB Output is correct
73 Correct 503 ms 32264 KB Output is correct
74 Correct 595 ms 45956 KB Output is correct
75 Correct 1134 ms 91144 KB Output is correct
76 Correct 1356 ms 81516 KB Output is correct
77 Correct 1070 ms 84868 KB Output is correct
78 Correct 469 ms 40876 KB Output is correct
79 Correct 693 ms 55432 KB Output is correct
80 Correct 684 ms 55244 KB Output is correct
81 Correct 537 ms 47736 KB Output is correct
82 Correct 730 ms 47336 KB Output is correct
83 Correct 112 ms 20816 KB Output is correct
84 Correct 692 ms 55472 KB Output is correct
85 Correct 644 ms 55108 KB Output is correct
86 Correct 532 ms 47744 KB Output is correct
87 Correct 554 ms 53144 KB Output is correct
88 Correct 472 ms 55424 KB Output is correct
89 Correct 460 ms 55376 KB Output is correct
90 Correct 440 ms 47900 KB Output is correct
91 Correct 546 ms 45516 KB Output is correct