oj.uz

Submission #732442

# Submission time Handle Problem Language Result Execution time Memory
732442 2023-04-29T04:26:05 Z SanguineChameleon Land of the Rainbow Gold (APIO17_rainbow) C++17
74 / 100
 3000 ms 330032 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

struct BIT {
	set<pair<int, int>> S;
	vector<unordered_map<int, int>> bit;
	int R, C;

	void init(int _R, int _C) {
		R = _R;
		C = _C;
		bit.resize(R + 1);
	}

	void add(int x, int y) {
		if (x < 1 || x > R || y < 1 || y > C || S.find({x, y}) != S.end()) {
			return;
		}
		S.insert({x, y});
	}

	void update(int x, int y) {
		for (int i = x; i <= R; i += i & (-i)) {
			for (int j = y; j <= C; j += j & (-j)) {
				bit[i][j]++;
			}
		}
	}

	void build() {
		for (auto p: S) {
			int x = p.first;
			int y = p.second;
			update(x, y);
		}
	}

	int get(int x, int y) {
		int res = 0;
		for (int i = x; i > 0; i -= i & (-i)) {
			for (int j = y; j > 0; j -= j & (-j)) {
				auto it = bit[i].find(j);
				if (it != bit[i].end()) {
					res += it->second;
				}
			}
		}
		return res;
	}

	long long get(int lx, int ly, int rx, int ry) {
		return 1LL * (rx - lx + 1) * (ry - ly + 1) - get(rx, ry) + get(rx, ly - 1) + get(lx - 1, ry) - get(lx - 1, ly - 1);
	}

} V, row_E, col_E, F;

int max_X, min_X, max_Y, min_Y;

void add(int cx, int cy) {
	max_X = max(max_X, cx);
	min_X = min(min_X, cx);
	max_Y = max(max_Y, cy);
	min_Y = min(min_Y, cy);
	V.add(cx, cy);
	row_E.add(cx - 1, cy);
	row_E.add(cx, cy);
	col_E.add(cx, cy - 1);
	col_E.add(cx, cy);
	F.add(cx - 1, cy - 1);
	F.add(cx - 1, cy);
	F.add(cx, cy - 1);
	F.add(cx, cy);
}

void init(int R, int C, int cx, int cy, int M, char *S) {
	V.init(R, C);
	row_E.init(R, C);
	col_E.init(R, C);
	F.init(R, C);
	max_X = cx;
	min_X = cx;
	max_Y = cy;
	min_Y = cy;
	add(cx, cy);
	for (int i = 0; i < M; i++) {
		if (S[i] == 'N') {
			cx--;
		}
		if (S[i] == 'E') {
			cy++;
		}
		if (S[i] == 'S') {
			cx++;
		}
		if (S[i] == 'W') {
			cy--;
		}
		add(cx, cy);
	}
	V.build();
	row_E.build();
	col_E.build();
	F.build();
}

int colour(int lx, int ly, int rx, int ry) {
	return V.get(lx, ly, rx, ry) - row_E.get(lx, ly, rx - 1, ry) - col_E.get(lx, ly, rx, ry - 1) + F.get(lx, ly, rx - 1, ry - 1) + (lx < min_X && max_X < rx && ly < min_Y && max_Y < ry);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 5 ms 724 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 6 ms 980 KB Output is correct
14 Correct 8 ms 1116 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 426 ms 32948 KB Output is correct
4 Correct 552 ms 56204 KB Output is correct
5 Correct 564 ms 55048 KB Output is correct
6 Correct 535 ms 36140 KB Output is correct
7 Correct 418 ms 35488 KB Output is correct
8 Correct 189 ms 1080 KB Output is correct
9 Correct 555 ms 56152 KB Output is correct
10 Correct 574 ms 55136 KB Output is correct
11 Correct 506 ms 36240 KB Output is correct
12 Correct 412 ms 53192 KB Output is correct
13 Correct 395 ms 56208 KB Output is correct
14 Correct 421 ms 55172 KB Output is correct
15 Correct 353 ms 36252 KB Output is correct
16 Correct 501 ms 38000 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1692 ms 225032 KB Output is correct
3 Correct 1121 ms 222708 KB Output is correct
4 Correct 1818 ms 260000 KB Output is correct
5 Correct 1175 ms 195616 KB Output is correct
6 Correct 301 ms 56416 KB Output is correct
7 Correct 478 ms 66996 KB Output is correct
8 Correct 376 ms 52368 KB Output is correct
9 Correct 357 ms 53596 KB Output is correct
10 Correct 132 ms 33848 KB Output is correct
11 Correct 346 ms 63844 KB Output is correct
12 Correct 1790 ms 224944 KB Output is correct
13 Correct 1119 ms 222856 KB Output is correct
14 Correct 1910 ms 259928 KB Output is correct
15 Correct 1166 ms 195388 KB Output is correct
16 Correct 285 ms 54020 KB Output is correct
17 Correct 546 ms 67340 KB Output is correct
18 Correct 2222 ms 103436 KB Output is correct
19 Correct 1756 ms 312352 KB Output is correct
20 Correct 2041 ms 329916 KB Output is correct
21 Correct 351 ms 52272 KB Output is correct
22 Correct 360 ms 53564 KB Output is correct
23 Correct 138 ms 33780 KB Output is correct
24 Correct 326 ms 63916 KB Output is correct
25 Correct 1687 ms 225092 KB Output is correct
26 Correct 1118 ms 222916 KB Output is correct
27 Correct 1887 ms 259872 KB Output is correct
28 Correct 1133 ms 195492 KB Output is correct
29 Correct 285 ms 53984 KB Output is correct
30 Correct 545 ms 67436 KB Output is correct
31 Correct 2207 ms 103308 KB Output is correct
32 Correct 1778 ms 312452 KB Output is correct
33 Correct 1971 ms 330032 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 5 ms 724 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 6 ms 980 KB Output is correct
14 Correct 8 ms 1116 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1378 ms 45592 KB Output is correct
19 Correct 364 ms 3400 KB Output is correct
20 Correct 206 ms 1356 KB Output is correct
21 Correct 287 ms 1812 KB Output is correct
22 Correct 323 ms 2484 KB Output is correct
23 Correct 362 ms 3244 KB Output is correct
24 Correct 223 ms 1560 KB Output is correct
25 Correct 302 ms 1996 KB Output is correct
26 Correct 328 ms 2656 KB Output is correct
27 Correct 810 ms 25840 KB Output is correct
28 Correct 600 ms 13724 KB Output is correct
29 Correct 673 ms 23108 KB Output is correct
30 Correct 1167 ms 59304 KB Output is correct
31 Correct 3 ms 340 KB Output is correct
32 Correct 755 ms 25104 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 5 ms 724 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 6 ms 980 KB Output is correct
14 Correct 8 ms 1116 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1378 ms 45592 KB Output is correct
19 Correct 364 ms 3400 KB Output is correct
20 Correct 206 ms 1356 KB Output is correct
21 Correct 287 ms 1812 KB Output is correct
22 Correct 323 ms 2484 KB Output is correct
23 Correct 362 ms 3244 KB Output is correct
24 Correct 223 ms 1560 KB Output is correct
25 Correct 302 ms 1996 KB Output is correct
26 Correct 328 ms 2656 KB Output is correct
27 Correct 810 ms 25840 KB Output is correct
28 Correct 600 ms 13724 KB Output is correct
29 Correct 673 ms 23108 KB Output is correct
30 Correct 1167 ms 59304 KB Output is correct
31 Correct 3 ms 340 KB Output is correct
32 Correct 755 ms 25104 KB Output is correct
33 Correct 1692 ms 225032 KB Output is correct
34 Correct 1121 ms 222708 KB Output is correct
35 Correct 1818 ms 260000 KB Output is correct
36 Correct 1175 ms 195616 KB Output is correct
37 Correct 301 ms 56416 KB Output is correct
38 Correct 478 ms 66996 KB Output is correct
39 Correct 376 ms 52368 KB Output is correct
40 Correct 357 ms 53596 KB Output is correct
41 Correct 132 ms 33848 KB Output is correct
42 Correct 346 ms 63844 KB Output is correct
43 Correct 1790 ms 224944 KB Output is correct
44 Correct 1119 ms 222856 KB Output is correct
45 Correct 1910 ms 259928 KB Output is correct
46 Correct 1166 ms 195388 KB Output is correct
47 Correct 285 ms 54020 KB Output is correct
48 Correct 546 ms 67340 KB Output is correct
49 Correct 2222 ms 103436 KB Output is correct
50 Correct 1756 ms 312352 KB Output is correct
51 Correct 2041 ms 329916 KB Output is correct
52 Correct 351 ms 52272 KB Output is correct
53 Correct 360 ms 53564 KB Output is correct
54 Correct 138 ms 33780 KB Output is correct
55 Correct 326 ms 63916 KB Output is correct
56 Correct 1687 ms 225092 KB Output is correct
57 Correct 1118 ms 222916 KB Output is correct
58 Correct 1887 ms 259872 KB Output is correct
59 Correct 1133 ms 195492 KB Output is correct
60 Correct 285 ms 53984 KB Output is correct
61 Correct 545 ms 67436 KB Output is correct
62 Correct 2207 ms 103308 KB Output is correct
63 Correct 1778 ms 312452 KB Output is correct
64 Correct 1971 ms 330032 KB Output is correct
65 Correct 426 ms 32948 KB Output is correct
66 Correct 552 ms 56204 KB Output is correct
67 Correct 564 ms 55048 KB Output is correct
68 Correct 535 ms 36140 KB Output is correct
69 Correct 418 ms 35488 KB Output is correct
70 Correct 189 ms 1080 KB Output is correct
71 Correct 555 ms 56152 KB Output is correct
72 Correct 574 ms 55136 KB Output is correct
73 Correct 506 ms 36240 KB Output is correct
74 Correct 412 ms 53192 KB Output is correct
75 Correct 395 ms 56208 KB Output is correct
76 Correct 421 ms 55172 KB Output is correct
77 Correct 353 ms 36252 KB Output is correct
78 Correct 501 ms 38000 KB Output is correct
79 Correct 729 ms 55840 KB Output is correct
80 Correct 865 ms 56984 KB Output is correct
81 Correct 717 ms 37324 KB Output is correct
82 Correct 1522 ms 67468 KB Output is correct
83 Correct 2961 ms 228580 KB Output is correct
84 Correct 2665 ms 226376 KB Output is correct
85 Execution timed out 3065 ms 262644 KB Time limit exceeded
86 Halted 0 ms 0 KB -