oj.uz

Submission #524214

# Submission time Handle Problem Language Result Execution time Memory
524214 2022-02-08T19:38:57 Z sidon Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 921 ms 112564 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(X) begin(X), end(X)
 
const int Z = 2e5+4;
 
template<const int n>
struct SegmentTree {
	vector<int> a[2*n];
	void insert(int i, int v) {
		a[i+n].push_back(v);
	}
	void build() {
		for(int i = n; i < 2*n; ++i) {
			sort(all(a[i]));
			a[i].erase(unique(all(a[i])), end(a[i]));
		}
		for(int i = n; --i; )
			merge(all(a[2*i]), all(a[2*i+1]), back_inserter(a[i]));
	}
	int getCnt(int i, int lv, int rv) {
		return upper_bound(all(a[i]), rv) - lower_bound(all(a[i]), lv);
	}
	int count(int l, int r, int lv, int rv) {
		int x = 0;
		for(l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if(l & 1) x += getCnt(l++, lv, rv);
			if(r & 1) x += getCnt(--r, lv, rv);
		}
		return x;
	}
};
 
SegmentTree<2*Z> edges;
SegmentTree<Z> cells, vertices;
int minR = Z, minC = Z, maxR, maxC;
 
void init(int R, int C, int uR, int uC, int M, char* S) {
	for(int i = 0; i <= M; ++i) {
		cells.insert(uC, uR);
		minR = min(minR, uR);
		minC = min(minC, uC);
		maxR = max(maxR, uR);
		maxC = max(maxC, uC);
		for(int x : {0, 1}) for(int y : {0, 1}) {
			vertices.insert(uC+x, uR+y);
		}
		for(int x : {0, 2}) {
			edges.insert(2*uC+x, 2*uR+1);
			edges.insert(2*uC+1, 2*uR+x);
		}
		if(i < M) {
			S[i] == 'S' ? ++uR : 0;
			S[i] == 'N' ? --uR : 0;
			S[i] == 'E' ? ++uC : 0;
			S[i] == 'W' ? --uC : 0;
		}
	}
	edges.build();
	cells.build();
	vertices.build();
}
 
int colour(int ar, int ac, int br, int bc) {
	bool add = ar < minR && ac < minC && br > maxR && bc > maxC;
	return edges.count(2*ac+1, 2*bc+1, 2*ar+1, 2*br+1) - vertices.count(ac+1, bc, ar+1, br) - cells.count(ac, bc, ar, br) + 1 + add;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 38012 KB Output is correct
2 Correct 28 ms 38468 KB Output is correct
3 Correct 26 ms 37956 KB Output is correct
4 Correct 27 ms 37980 KB Output is correct
5 Correct 33 ms 38576 KB Output is correct
6 Correct 25 ms 37836 KB Output is correct
7 Correct 24 ms 37800 KB Output is correct
8 Correct 25 ms 37756 KB Output is correct
9 Correct 27 ms 37776 KB Output is correct
10 Correct 25 ms 37812 KB Output is correct
11 Correct 27 ms 38012 KB Output is correct
12 Correct 28 ms 38220 KB Output is correct
13 Correct 29 ms 38592 KB Output is correct
14 Correct 30 ms 38916 KB Output is correct
15 Correct 27 ms 37952 KB Output is correct
16 Correct 27 ms 37888 KB Output is correct
17 Correct 26 ms 37876 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 37888 KB Output is correct
2 Correct 26 ms 37876 KB Output is correct
3 Correct 449 ms 79116 KB Output is correct
4 Correct 739 ms 112564 KB Output is correct
5 Correct 680 ms 110904 KB Output is correct
6 Correct 454 ms 92472 KB Output is correct
7 Correct 517 ms 91640 KB Output is correct
8 Correct 193 ms 43952 KB Output is correct
9 Correct 760 ms 112564 KB Output is correct
10 Correct 718 ms 111328 KB Output is correct
11 Correct 502 ms 92476 KB Output is correct
12 Correct 263 ms 102180 KB Output is correct
13 Correct 303 ms 112472 KB Output is correct
14 Correct 321 ms 111120 KB Output is correct
15 Correct 280 ms 92528 KB Output is correct
16 Correct 472 ms 87524 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 37952 KB Output is correct
2 Correct 167 ms 106600 KB Output is correct
3 Correct 95 ms 86776 KB Output is correct
4 Correct 128 ms 94760 KB Output is correct
5 Correct 102 ms 80476 KB Output is correct
6 Correct 68 ms 52084 KB Output is correct
7 Correct 80 ms 61508 KB Output is correct
8 Correct 130 ms 94484 KB Output is correct
9 Correct 121 ms 88124 KB Output is correct
10 Correct 57 ms 50804 KB Output is correct
11 Correct 92 ms 69708 KB Output is correct
12 Correct 161 ms 106672 KB Output is correct
13 Correct 95 ms 86772 KB Output is correct
14 Correct 130 ms 94772 KB Output is correct
15 Correct 104 ms 80528 KB Output is correct
16 Correct 65 ms 50256 KB Output is correct
17 Correct 79 ms 59896 KB Output is correct
18 Correct 97 ms 88016 KB Output is correct
19 Correct 128 ms 94720 KB Output is correct
20 Correct 129 ms 94812 KB Output is correct
21 Correct 129 ms 94460 KB Output is correct
22 Correct 118 ms 88148 KB Output is correct
23 Correct 54 ms 50820 KB Output is correct
24 Correct 92 ms 69744 KB Output is correct
25 Correct 163 ms 106580 KB Output is correct
26 Correct 95 ms 86848 KB Output is correct
27 Correct 128 ms 94840 KB Output is correct
28 Correct 100 ms 80508 KB Output is correct
29 Correct 66 ms 50440 KB Output is correct
30 Correct 79 ms 59840 KB Output is correct
31 Correct 99 ms 88016 KB Output is correct
32 Correct 128 ms 94740 KB Output is correct
33 Correct 129 ms 94828 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 38012 KB Output is correct
2 Correct 28 ms 38468 KB Output is correct
3 Correct 26 ms 37956 KB Output is correct
4 Correct 27 ms 37980 KB Output is correct
5 Correct 33 ms 38576 KB Output is correct
6 Correct 25 ms 37836 KB Output is correct
7 Correct 24 ms 37800 KB Output is correct
8 Correct 25 ms 37756 KB Output is correct
9 Correct 27 ms 37776 KB Output is correct
10 Correct 25 ms 37812 KB Output is correct
11 Correct 27 ms 38012 KB Output is correct
12 Correct 28 ms 38220 KB Output is correct
13 Correct 29 ms 38592 KB Output is correct
14 Correct 30 ms 38916 KB Output is correct
15 Correct 27 ms 37952 KB Output is correct
16 Correct 27 ms 37888 KB Output is correct
17 Correct 26 ms 37876 KB Output is correct
18 Correct 503 ms 70016 KB Output is correct
19 Correct 179 ms 42788 KB Output is correct
20 Correct 123 ms 41528 KB Output is correct
21 Correct 132 ms 41720 KB Output is correct
22 Correct 142 ms 42016 KB Output is correct
23 Correct 168 ms 42624 KB Output is correct
24 Correct 155 ms 41732 KB Output is correct
25 Correct 171 ms 42056 KB Output is correct
26 Correct 160 ms 42296 KB Output is correct
27 Correct 253 ms 65788 KB Output is correct
28 Correct 234 ms 55996 KB Output is correct
29 Correct 308 ms 64216 KB Output is correct
30 Correct 454 ms 91596 KB Output is correct
31 Correct 27 ms 37896 KB Output is correct
32 Correct 453 ms 67192 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 38012 KB Output is correct
2 Correct 28 ms 38468 KB Output is correct
3 Correct 26 ms 37956 KB Output is correct
4 Correct 27 ms 37980 KB Output is correct
5 Correct 33 ms 38576 KB Output is correct
6 Correct 25 ms 37836 KB Output is correct
7 Correct 24 ms 37800 KB Output is correct
8 Correct 25 ms 37756 KB Output is correct
9 Correct 27 ms 37776 KB Output is correct
10 Correct 25 ms 37812 KB Output is correct
11 Correct 27 ms 38012 KB Output is correct
12 Correct 28 ms 38220 KB Output is correct
13 Correct 29 ms 38592 KB Output is correct
14 Correct 30 ms 38916 KB Output is correct
15 Correct 27 ms 37952 KB Output is correct
16 Correct 27 ms 37888 KB Output is correct
17 Correct 26 ms 37876 KB Output is correct
18 Correct 503 ms 70016 KB Output is correct
19 Correct 179 ms 42788 KB Output is correct
20 Correct 123 ms 41528 KB Output is correct
21 Correct 132 ms 41720 KB Output is correct
22 Correct 142 ms 42016 KB Output is correct
23 Correct 168 ms 42624 KB Output is correct
24 Correct 155 ms 41732 KB Output is correct
25 Correct 171 ms 42056 KB Output is correct
26 Correct 160 ms 42296 KB Output is correct
27 Correct 253 ms 65788 KB Output is correct
28 Correct 234 ms 55996 KB Output is correct
29 Correct 308 ms 64216 KB Output is correct
30 Correct 454 ms 91596 KB Output is correct
31 Correct 27 ms 37896 KB Output is correct
32 Correct 453 ms 67192 KB Output is correct
33 Correct 167 ms 106600 KB Output is correct
34 Correct 95 ms 86776 KB Output is correct
35 Correct 128 ms 94760 KB Output is correct
36 Correct 102 ms 80476 KB Output is correct
37 Correct 68 ms 52084 KB Output is correct
38 Correct 80 ms 61508 KB Output is correct
39 Correct 130 ms 94484 KB Output is correct
40 Correct 121 ms 88124 KB Output is correct
41 Correct 57 ms 50804 KB Output is correct
42 Correct 92 ms 69708 KB Output is correct
43 Correct 161 ms 106672 KB Output is correct
44 Correct 95 ms 86772 KB Output is correct
45 Correct 130 ms 94772 KB Output is correct
46 Correct 104 ms 80528 KB Output is correct
47 Correct 65 ms 50256 KB Output is correct
48 Correct 79 ms 59896 KB Output is correct
49 Correct 97 ms 88016 KB Output is correct
50 Correct 128 ms 94720 KB Output is correct
51 Correct 129 ms 94812 KB Output is correct
52 Correct 129 ms 94460 KB Output is correct
53 Correct 118 ms 88148 KB Output is correct
54 Correct 54 ms 50820 KB Output is correct
55 Correct 92 ms 69744 KB Output is correct
56 Correct 163 ms 106580 KB Output is correct
57 Correct 95 ms 86848 KB Output is correct
58 Correct 128 ms 94840 KB Output is correct
59 Correct 100 ms 80508 KB Output is correct
60 Correct 66 ms 50440 KB Output is correct
61 Correct 79 ms 59840 KB Output is correct
62 Correct 99 ms 88016 KB Output is correct
63 Correct 128 ms 94740 KB Output is correct
64 Correct 129 ms 94828 KB Output is correct
65 Correct 449 ms 79116 KB Output is correct
66 Correct 739 ms 112564 KB Output is correct
67 Correct 680 ms 110904 KB Output is correct
68 Correct 454 ms 92472 KB Output is correct
69 Correct 517 ms 91640 KB Output is correct
70 Correct 193 ms 43952 KB Output is correct
71 Correct 760 ms 112564 KB Output is correct
72 Correct 718 ms 111328 KB Output is correct
73 Correct 502 ms 92476 KB Output is correct
74 Correct 263 ms 102180 KB Output is correct
75 Correct 303 ms 112472 KB Output is correct
76 Correct 321 ms 111120 KB Output is correct
77 Correct 280 ms 92528 KB Output is correct
78 Correct 472 ms 87524 KB Output is correct
79 Correct 907 ms 98024 KB Output is correct
80 Correct 921 ms 91740 KB Output is correct
81 Correct 361 ms 54208 KB Output is correct
82 Correct 485 ms 73224 KB Output is correct
83 Correct 523 ms 110132 KB Output is correct
84 Correct 276 ms 90324 KB Output is correct
85 Correct 336 ms 98328 KB Output is correct
86 Correct 308 ms 83936 KB Output is correct
87 Correct 214 ms 53820 KB Output is correct
88 Correct 254 ms 63376 KB Output is correct
89 Correct 243 ms 91544 KB Output is correct
90 Correct 401 ms 98528 KB Output is correct
91 Correct 407 ms 98332 KB Output is correct