oj.uz

Submission #991966

# Submission time Handle Problem Language Result Execution time Memory
991966 2024-06-03T13:08:58 Z pubin06 Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 618 ms 197004 KB 
#include <bits/stdc++.h>
#define sz(v) (int)(v).size()
using namespace std;
 
const int MXn = 2e5 + 5;
const int dx[] = {1, 0, 1};
const int dy[] = {0, 1, 1};
 
int n, m;
struct PST {
	vector<int> val, idL, idR;
	void resiz(int s) {
		val.resize(s + 3, 0);
		idL.resize(s + 3, -1);
		idR.resize(s + 3, -1);
	}
	int no = 0;
	int build(int l = 1, int r = n) {
		int cur = ++no;
		assert(cur < sz(val));
		val[cur] = 0;
		if (l == r) return cur;
		int mid = (l + r) >> 1;
		idL[cur] = build(l, mid);
		idR[cur] = build(mid + 1, r);
		return cur;
	}
	int update(int i, int v, int oID, int l = 1, int r = n) {
		int cur = ++no;
		assert(cur < sz(val));
		if (l == r) {
			val[cur] = val[oID] + v;
			return cur;
		}
		int mid = (l + r) >> 1;
		if (i <= mid) {
			idL[cur] = update(i, v, idL[oID], l, mid);
			idR[cur] = idR[oID];
		} else {
			idL[cur] = idL[oID];
			idR[cur] = update(i, v, idR[oID], mid + 1, r);
		}
		val[cur] = val[idL[cur]] + val[idR[cur]];
		return cur;
	}
	int get(int Lf, int Rt, int id, int l = 1, int r = n) {
		if (Lf <= l && r <= Rt) {
			return val[id];
		}
		int mid = (l + r) >> 1;
		int res = 0;
		if (Lf <= mid) res += get(Lf, Rt, idL[id], l, mid);
		if (Rt > mid) res += get(Lf, Rt, idR[id], mid + 1, r);
		return res;
	}
} T[4];
int root[4][MXn];
 
bool onboard(int x, int y) {
	return 1 <= x && x <= n && 1 <= y && y <= m;
}
vector<int> river[MXn], v1[MXn], v2[MXn], v3[MXn];
int xmin = MXn, xmax = -MXn, ymin = MXn, ymax = -MXn;
void add(int sr, int sc) {
	xmin = min(xmin, sr);
	xmax = max(xmax, sr);
	ymin = min(ymin, sc);
	ymax = max(ymax, sc);
    assert(onboard(sr, sc));
	river[sc].emplace_back(sr);
	if (sc > 1) v1[sc - 1].emplace_back(sr);
	v1[sc].emplace_back(sr);
	if (sr > 1) v2[sc].emplace_back(sr - 1);
	v2[sc].emplace_back(sr);
	v3[sc].emplace_back(sr);
	for (int k = 0; k < 3; k++) {
		int xx = dx[k] + sr, yy = dy[k] + sc;
		if (onboard(xx, yy)) v3[yy].emplace_back(xx);
	}
}
void init(int R, int C, int sr, int sc, int M, char *S) {
	n = R, m = C;
	add(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++;
		add(sr, sc);
	}
	vector<int> siz(4, 0);
	for (int c = 1; c <= C; c++) {
		sort(begin(river[c]), end(river[c]));
		river[c].resize(unique(begin(river[c]), end(river[c])) - river[c].begin());
		siz[0] += sz(river[c]);
		sort(begin(v1[c]), end(v1[c]));
		v1[c].resize(unique(begin(v1[c]), end(v1[c])) - v1[c].begin());
		siz[1] += sz(v1[c]);
		sort(begin(v2[c]), end(v2[c]));
		v2[c].resize(unique(begin(v2[c]), end(v2[c])) - v2[c].begin());
		siz[2] += sz(v2[c]);
		sort(begin(v3[c]), end(v3[c]));
		v3[c].resize(unique(begin(v3[c]), end(v3[c])) - v3[c].begin());
		siz[3] += sz(v3[c]);
	}
	for (int t = 0; t < 4; t++) {
		T[t].resiz((1 << 19) + siz[t] * 19);
		root[t][0] = T[t].build();
	}
	for (int c = 1; c <= C; c++) {
		root[0][c] = root[0][c - 1];
		root[1][c] = root[1][c - 1];
		root[2][c] = root[2][c - 1];
		root[3][c] = root[3][c - 1];
		
		for (int r: river[c]) {
			root[0][c] = T[0].update(r, 1, root[0][c]);
		}
		for (int r: v1[c]) {
			root[1][c] = T[1].update(r, 1, root[1][c]);
		}
		for (int r: v2[c]) {
			root[2][c] = T[2].update(r, 1, root[2][c]);
		}
		for (int r: v3[c]) {
			root[3][c] = T[3].update(r, 1, root[3][c]);
		}
	}
}
 
int colour(int ar, int ac, int br, int bc) {
	long long V = (br - ar + 1) * (bc - ac + 1) - (T[0].get(ar, br, root[0][bc]) - T[0].get(ar, br, root[0][ac - 1]));
	long long E = (bc - ac) * (br - ar + 1) - (T[1].get(ar, br, root[1][bc - 1]) - T[1].get(ar, br, root[1][ac - 1])) + (bc - ac + 1) * (br - ar);
 	long long F = 0;
 	if (ar < br) {
 	    E -= (T[2].get(ar, br - 1, root[2][bc]) - T[2].get(ar, br - 1, root[2][ac - 1]));
 	    F = (br - ar) * (bc - ac) - (T[3].get(ar + 1, br, root[3][bc]) - T[3].get(ar + 1, br, root[3][ac]));
 	}
 	if (ar < xmin && xmax < br && ac < ymin && ymax < bc) F++;
 	// cerr << x1 << ' ' << ymin << ' ' << xmax << ' ' << ymax << '\n';
 	// cerr << V << ' ' << E << ' ' << F << '\n';
 	return V - E + F;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 45916 KB Output is correct
2 Correct 15 ms 46940 KB Output is correct
3 Correct 16 ms 45916 KB Output is correct
4 Correct 14 ms 45916 KB Output is correct
5 Correct 17 ms 47196 KB Output is correct
6 Correct 19 ms 45660 KB Output is correct
7 Correct 19 ms 45660 KB Output is correct
8 Correct 15 ms 45660 KB Output is correct
9 Correct 15 ms 45728 KB Output is correct
10 Correct 14 ms 45660 KB Output is correct
11 Correct 16 ms 46172 KB Output is correct
12 Correct 16 ms 46684 KB Output is correct
13 Correct 15 ms 47452 KB Output is correct
14 Correct 16 ms 47964 KB Output is correct
15 Correct 13 ms 45660 KB Output is correct
16 Correct 14 ms 45660 KB Output is correct
17 Correct 14 ms 45660 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 45660 KB Output is correct
2 Correct 14 ms 45660 KB Output is correct
3 Correct 91 ms 124360 KB Output is correct
4 Correct 112 ms 174044 KB Output is correct
5 Correct 109 ms 171600 KB Output is correct
6 Correct 95 ms 140112 KB Output is correct
7 Correct 96 ms 135736 KB Output is correct
8 Correct 64 ms 54308 KB Output is correct
9 Correct 107 ms 174076 KB Output is correct
10 Correct 106 ms 171556 KB Output is correct
11 Correct 119 ms 140116 KB Output is correct
12 Correct 99 ms 165716 KB Output is correct
13 Correct 98 ms 173924 KB Output is correct
14 Correct 98 ms 171564 KB Output is correct
15 Correct 91 ms 140140 KB Output is correct
16 Correct 92 ms 138204 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45660 KB Output is correct
2 Correct 155 ms 193504 KB Output is correct
3 Correct 162 ms 184996 KB Output is correct
4 Correct 166 ms 187984 KB Output is correct
5 Correct 106 ms 153220 KB Output is correct
6 Correct 70 ms 77140 KB Output is correct
7 Correct 83 ms 102228 KB Output is correct
8 Correct 64 ms 155472 KB Output is correct
9 Correct 61 ms 145748 KB Output is correct
10 Correct 50 ms 74328 KB Output is correct
11 Correct 79 ms 112800 KB Output is correct
12 Correct 158 ms 193360 KB Output is correct
13 Correct 172 ms 185000 KB Output is correct
14 Correct 177 ms 188076 KB Output is correct
15 Correct 112 ms 153220 KB Output is correct
16 Correct 59 ms 72268 KB Output is correct
17 Correct 79 ms 101964 KB Output is correct
18 Correct 155 ms 185604 KB Output is correct
19 Correct 122 ms 177848 KB Output is correct
20 Correct 120 ms 177628 KB Output is correct
21 Correct 72 ms 155476 KB Output is correct
22 Correct 79 ms 145748 KB Output is correct
23 Correct 45 ms 74472 KB Output is correct
24 Correct 73 ms 112728 KB Output is correct
25 Correct 165 ms 193364 KB Output is correct
26 Correct 169 ms 185064 KB Output is correct
27 Correct 168 ms 187988 KB Output is correct
28 Correct 108 ms 153224 KB Output is correct
29 Correct 58 ms 72268 KB Output is correct
30 Correct 81 ms 101860 KB Output is correct
31 Correct 168 ms 185496 KB Output is correct
32 Correct 127 ms 177848 KB Output is correct
33 Correct 122 ms 177668 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 45916 KB Output is correct
2 Correct 15 ms 46940 KB Output is correct
3 Correct 16 ms 45916 KB Output is correct
4 Correct 14 ms 45916 KB Output is correct
5 Correct 17 ms 47196 KB Output is correct
6 Correct 19 ms 45660 KB Output is correct
7 Correct 19 ms 45660 KB Output is correct
8 Correct 15 ms 45660 KB Output is correct
9 Correct 15 ms 45728 KB Output is correct
10 Correct 14 ms 45660 KB Output is correct
11 Correct 16 ms 46172 KB Output is correct
12 Correct 16 ms 46684 KB Output is correct
13 Correct 15 ms 47452 KB Output is correct
14 Correct 16 ms 47964 KB Output is correct
15 Correct 13 ms 45660 KB Output is correct
16 Correct 14 ms 45660 KB Output is correct
17 Correct 14 ms 45660 KB Output is correct
18 Correct 348 ms 120660 KB Output is correct
19 Correct 116 ms 52304 KB Output is correct
20 Correct 101 ms 49744 KB Output is correct
21 Correct 116 ms 50260 KB Output is correct
22 Correct 130 ms 50760 KB Output is correct
23 Correct 122 ms 52308 KB Output is correct
24 Correct 103 ms 50260 KB Output is correct
25 Correct 119 ms 50768 KB Output is correct
26 Correct 160 ms 51280 KB Output is correct
27 Correct 211 ms 108932 KB Output is correct
28 Correct 196 ms 80720 KB Output is correct
29 Correct 215 ms 104532 KB Output is correct
30 Correct 325 ms 187724 KB Output is correct
31 Correct 15 ms 45912 KB Output is correct
32 Correct 314 ms 110164 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 45916 KB Output is correct
2 Correct 15 ms 46940 KB Output is correct
3 Correct 16 ms 45916 KB Output is correct
4 Correct 14 ms 45916 KB Output is correct
5 Correct 17 ms 47196 KB Output is correct
6 Correct 19 ms 45660 KB Output is correct
7 Correct 19 ms 45660 KB Output is correct
8 Correct 15 ms 45660 KB Output is correct
9 Correct 15 ms 45728 KB Output is correct
10 Correct 14 ms 45660 KB Output is correct
11 Correct 16 ms 46172 KB Output is correct
12 Correct 16 ms 46684 KB Output is correct
13 Correct 15 ms 47452 KB Output is correct
14 Correct 16 ms 47964 KB Output is correct
15 Correct 13 ms 45660 KB Output is correct
16 Correct 14 ms 45660 KB Output is correct
17 Correct 14 ms 45660 KB Output is correct
18 Correct 348 ms 120660 KB Output is correct
19 Correct 116 ms 52304 KB Output is correct
20 Correct 101 ms 49744 KB Output is correct
21 Correct 116 ms 50260 KB Output is correct
22 Correct 130 ms 50760 KB Output is correct
23 Correct 122 ms 52308 KB Output is correct
24 Correct 103 ms 50260 KB Output is correct
25 Correct 119 ms 50768 KB Output is correct
26 Correct 160 ms 51280 KB Output is correct
27 Correct 211 ms 108932 KB Output is correct
28 Correct 196 ms 80720 KB Output is correct
29 Correct 215 ms 104532 KB Output is correct
30 Correct 325 ms 187724 KB Output is correct
31 Correct 15 ms 45912 KB Output is correct
32 Correct 314 ms 110164 KB Output is correct
33 Correct 155 ms 193504 KB Output is correct
34 Correct 162 ms 184996 KB Output is correct
35 Correct 166 ms 187984 KB Output is correct
36 Correct 106 ms 153220 KB Output is correct
37 Correct 70 ms 77140 KB Output is correct
38 Correct 83 ms 102228 KB Output is correct
39 Correct 64 ms 155472 KB Output is correct
40 Correct 61 ms 145748 KB Output is correct
41 Correct 50 ms 74328 KB Output is correct
42 Correct 79 ms 112800 KB Output is correct
43 Correct 158 ms 193360 KB Output is correct
44 Correct 172 ms 185000 KB Output is correct
45 Correct 177 ms 188076 KB Output is correct
46 Correct 112 ms 153220 KB Output is correct
47 Correct 59 ms 72268 KB Output is correct
48 Correct 79 ms 101964 KB Output is correct
49 Correct 155 ms 185604 KB Output is correct
50 Correct 122 ms 177848 KB Output is correct
51 Correct 120 ms 177628 KB Output is correct
52 Correct 72 ms 155476 KB Output is correct
53 Correct 79 ms 145748 KB Output is correct
54 Correct 45 ms 74472 KB Output is correct
55 Correct 73 ms 112728 KB Output is correct
56 Correct 165 ms 193364 KB Output is correct
57 Correct 169 ms 185064 KB Output is correct
58 Correct 168 ms 187988 KB Output is correct
59 Correct 108 ms 153224 KB Output is correct
60 Correct 58 ms 72268 KB Output is correct
61 Correct 81 ms 101860 KB Output is correct
62 Correct 168 ms 185496 KB Output is correct
63 Correct 127 ms 177848 KB Output is correct
64 Correct 122 ms 177668 KB Output is correct
65 Correct 91 ms 124360 KB Output is correct
66 Correct 112 ms 174044 KB Output is correct
67 Correct 109 ms 171600 KB Output is correct
68 Correct 95 ms 140112 KB Output is correct
69 Correct 96 ms 135736 KB Output is correct
70 Correct 64 ms 54308 KB Output is correct
71 Correct 107 ms 174076 KB Output is correct
72 Correct 106 ms 171556 KB Output is correct
73 Correct 119 ms 140116 KB Output is correct
74 Correct 99 ms 165716 KB Output is correct
75 Correct 98 ms 173924 KB Output is correct
76 Correct 98 ms 171564 KB Output is correct
77 Correct 91 ms 140140 KB Output is correct
78 Correct 92 ms 138204 KB Output is correct
79 Correct 136 ms 158888 KB Output is correct
80 Correct 156 ms 149248 KB Output is correct
81 Correct 185 ms 78160 KB Output is correct
82 Correct 261 ms 116272 KB Output is correct
83 Correct 610 ms 197004 KB Output is correct
84 Correct 618 ms 188560 KB Output is correct
85 Correct 565 ms 191632 KB Output is correct
86 Correct 558 ms 156808 KB Output is correct
87 Correct 373 ms 75600 KB Output is correct
88 Correct 428 ms 105456 KB Output is correct
89 Correct 529 ms 189116 KB Output is correct
90 Correct 564 ms 181428 KB Output is correct
91 Correct 524 ms 181356 KB Output is correct