oj.uz

Submission #562181

# Submission time Handle Problem Language Result Execution time Memory
562181 2022-05-14T06:57:16 Z hollwo_pelw Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 1018 ms 77752 KB 
#include "rainbow.h"

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int min_X, min_Y, max_X, max_Y, tomap[1 << 8];

struct data_t {
	vector<pair<int, int>> list_val;
	vector<int> val[N];
	inline void pre_add(int x, int y) {
		// x -= min_X - 1, y -= min_Y - 1;
		list_val.emplace_back(x, y);
	}

	inline void work() {
		sort(list_val.begin(), list_val.end());
		list_val.erase(unique(list_val.begin(), list_val.end()), list_val.end());

		for (auto [x, y] : list_val) {
			for (; x < N; x += x & -x)
				val[x].push_back(y);
		}

		for (int i = 1; i < N; i++)
			sort(val[i].begin(), val[i].end());
	}

	inline int count(int p, int l, int r) {
		int res = 0;
		for (p = min(p, N - 1); p > 0; p -= p & -p) {
			res += upper_bound(val[p].begin(), val[p].end(), r)
				 - lower_bound(val[p].begin(), val[p].end(), l);
		}
		return res;
	}

	inline int count(int ax, int ay, int bx, int by) {
		// ax -= min_X - 1;
		// ay -= min_Y - 1;
		// bx -= min_X - 1;
		// by -= min_Y - 1;
		return count(bx, ay, by) - count(ax - 1, ay, by);
	}
} c11, c12, c21, c22;

void init(int X, int Y, int x, int y, int M, char *S) {
	tomap['N'] = 0;
	tomap['E'] = 1;
	tomap['S'] = 2;
	tomap['W'] = 3;

	vector<pair<int, int>> path;
	path.emplace_back(x, y);

	min_X = max_X = x;
	min_Y = max_Y = y;

	for (int i = 0; i < M; i++) {
		x += dx[tomap[S[i]]];
		y += dy[tomap[S[i]]];
		path.emplace_back(x, y);
	}

	for (auto [x, y] : path) {
		min_X = min(min_X, x);
		max_X = max(max_X, x);
		min_Y = min(min_Y, y);
		max_Y = max(max_Y, y);

		c11.pre_add(x, y);
		
		c12.pre_add(x, y);
		c12.pre_add(x, y + 1);

		c21.pre_add(x, y);
		c21.pre_add(x + 1, y);

		c22.pre_add(x, y);
		c22.pre_add(x, y + 1);
		c22.pre_add(x + 1, y);
		c22.pre_add(x + 1, y + 1);
	}

	c11.work();
	c12.work();
	c21.work();
	c22.work();
}

int colour(int ax, int ay, int bx, int by) {
	int res = (ax < min_X && ay < min_Y && bx > max_X && by > max_Y) ? 2 : 1;

	res -= c11.count(ax, ay, bx, by);
	res += c12.count(ax, ay + 1, bx, by);
	res += c21.count(ax + 1, ay, bx, by);
	res -= c22.count(ax + 1, ay + 1, bx, by);

	return res;
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:64:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   64 |   x += dx[tomap[S[i]]];
      |                 ~~~^
rainbow.cpp:65:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   65 |   y += dy[tomap[S[i]]];
      |                 ~~~^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19156 KB Output is correct
2 Correct 18 ms 19620 KB Output is correct
3 Correct 13 ms 19284 KB Output is correct
4 Correct 15 ms 19256 KB Output is correct
5 Correct 18 ms 19732 KB Output is correct
6 Correct 11 ms 19076 KB Output is correct
7 Correct 11 ms 19096 KB Output is correct
8 Correct 12 ms 19156 KB Output is correct
9 Correct 11 ms 19028 KB Output is correct
10 Correct 12 ms 19028 KB Output is correct
11 Correct 14 ms 19292 KB Output is correct
12 Correct 17 ms 19492 KB Output is correct
13 Correct 19 ms 19924 KB Output is correct
14 Correct 22 ms 20280 KB Output is correct
15 Correct 12 ms 19028 KB Output is correct
16 Correct 13 ms 19104 KB Output is correct
17 Correct 16 ms 19088 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19104 KB Output is correct
2 Correct 16 ms 19088 KB Output is correct
3 Correct 519 ms 52652 KB Output is correct
4 Correct 796 ms 77728 KB Output is correct
5 Correct 818 ms 77600 KB Output is correct
6 Correct 666 ms 72536 KB Output is correct
7 Correct 636 ms 67952 KB Output is correct
8 Correct 99 ms 30368 KB Output is correct
9 Correct 699 ms 77732 KB Output is correct
10 Correct 778 ms 77728 KB Output is correct
11 Correct 647 ms 72420 KB Output is correct
12 Correct 792 ms 76064 KB Output is correct
13 Correct 681 ms 77752 KB Output is correct
14 Correct 678 ms 77592 KB Output is correct
15 Correct 601 ms 72508 KB Output is correct
16 Correct 652 ms 69192 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 389 ms 53344 KB Output is correct
3 Correct 162 ms 57448 KB Output is correct
4 Correct 195 ms 57140 KB Output is correct
5 Correct 182 ms 48048 KB Output is correct
6 Correct 114 ms 32644 KB Output is correct
7 Correct 153 ms 35484 KB Output is correct
8 Correct 496 ms 72052 KB Output is correct
9 Correct 460 ms 68516 KB Output is correct
10 Correct 99 ms 29316 KB Output is correct
11 Correct 193 ms 41272 KB Output is correct
12 Correct 384 ms 53344 KB Output is correct
13 Correct 157 ms 57396 KB Output is correct
14 Correct 179 ms 57260 KB Output is correct
15 Correct 200 ms 47960 KB Output is correct
16 Correct 108 ms 31624 KB Output is correct
17 Correct 166 ms 39060 KB Output is correct
18 Correct 419 ms 66288 KB Output is correct
19 Correct 266 ms 56832 KB Output is correct
20 Correct 318 ms 60532 KB Output is correct
21 Correct 539 ms 72052 KB Output is correct
22 Correct 476 ms 68488 KB Output is correct
23 Correct 92 ms 29288 KB Output is correct
24 Correct 189 ms 41208 KB Output is correct
25 Correct 399 ms 53340 KB Output is correct
26 Correct 165 ms 57492 KB Output is correct
27 Correct 192 ms 57228 KB Output is correct
28 Correct 190 ms 47948 KB Output is correct
29 Correct 111 ms 31644 KB Output is correct
30 Correct 179 ms 39164 KB Output is correct
31 Correct 434 ms 66404 KB Output is correct
32 Correct 279 ms 56900 KB Output is correct
33 Correct 396 ms 60424 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19156 KB Output is correct
2 Correct 18 ms 19620 KB Output is correct
3 Correct 13 ms 19284 KB Output is correct
4 Correct 15 ms 19256 KB Output is correct
5 Correct 18 ms 19732 KB Output is correct
6 Correct 11 ms 19076 KB Output is correct
7 Correct 11 ms 19096 KB Output is correct
8 Correct 12 ms 19156 KB Output is correct
9 Correct 11 ms 19028 KB Output is correct
10 Correct 12 ms 19028 KB Output is correct
11 Correct 14 ms 19292 KB Output is correct
12 Correct 17 ms 19492 KB Output is correct
13 Correct 19 ms 19924 KB Output is correct
14 Correct 22 ms 20280 KB Output is correct
15 Correct 12 ms 19028 KB Output is correct
16 Correct 13 ms 19104 KB Output is correct
17 Correct 16 ms 19088 KB Output is correct
18 Correct 1018 ms 48020 KB Output is correct
19 Correct 266 ms 23992 KB Output is correct
20 Correct 182 ms 22708 KB Output is correct
21 Correct 235 ms 22968 KB Output is correct
22 Correct 244 ms 23260 KB Output is correct
23 Correct 233 ms 24008 KB Output is correct
24 Correct 243 ms 23072 KB Output is correct
25 Correct 235 ms 23344 KB Output is correct
26 Correct 253 ms 23488 KB Output is correct
27 Correct 392 ms 44872 KB Output is correct
28 Correct 364 ms 36648 KB Output is correct
29 Correct 370 ms 42276 KB Output is correct
30 Correct 849 ms 69016 KB Output is correct
31 Correct 16 ms 19284 KB Output is correct
32 Correct 624 ms 47128 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19156 KB Output is correct
2 Correct 18 ms 19620 KB Output is correct
3 Correct 13 ms 19284 KB Output is correct
4 Correct 15 ms 19256 KB Output is correct
5 Correct 18 ms 19732 KB Output is correct
6 Correct 11 ms 19076 KB Output is correct
7 Correct 11 ms 19096 KB Output is correct
8 Correct 12 ms 19156 KB Output is correct
9 Correct 11 ms 19028 KB Output is correct
10 Correct 12 ms 19028 KB Output is correct
11 Correct 14 ms 19292 KB Output is correct
12 Correct 17 ms 19492 KB Output is correct
13 Correct 19 ms 19924 KB Output is correct
14 Correct 22 ms 20280 KB Output is correct
15 Correct 12 ms 19028 KB Output is correct
16 Correct 13 ms 19104 KB Output is correct
17 Correct 16 ms 19088 KB Output is correct
18 Correct 1018 ms 48020 KB Output is correct
19 Correct 266 ms 23992 KB Output is correct
20 Correct 182 ms 22708 KB Output is correct
21 Correct 235 ms 22968 KB Output is correct
22 Correct 244 ms 23260 KB Output is correct
23 Correct 233 ms 24008 KB Output is correct
24 Correct 243 ms 23072 KB Output is correct
25 Correct 235 ms 23344 KB Output is correct
26 Correct 253 ms 23488 KB Output is correct
27 Correct 392 ms 44872 KB Output is correct
28 Correct 364 ms 36648 KB Output is correct
29 Correct 370 ms 42276 KB Output is correct
30 Correct 849 ms 69016 KB Output is correct
31 Correct 16 ms 19284 KB Output is correct
32 Correct 624 ms 47128 KB Output is correct
33 Correct 389 ms 53344 KB Output is correct
34 Correct 162 ms 57448 KB Output is correct
35 Correct 195 ms 57140 KB Output is correct
36 Correct 182 ms 48048 KB Output is correct
37 Correct 114 ms 32644 KB Output is correct
38 Correct 153 ms 35484 KB Output is correct
39 Correct 496 ms 72052 KB Output is correct
40 Correct 460 ms 68516 KB Output is correct
41 Correct 99 ms 29316 KB Output is correct
42 Correct 193 ms 41272 KB Output is correct
43 Correct 384 ms 53344 KB Output is correct
44 Correct 157 ms 57396 KB Output is correct
45 Correct 179 ms 57260 KB Output is correct
46 Correct 200 ms 47960 KB Output is correct
47 Correct 108 ms 31624 KB Output is correct
48 Correct 166 ms 39060 KB Output is correct
49 Correct 419 ms 66288 KB Output is correct
50 Correct 266 ms 56832 KB Output is correct
51 Correct 318 ms 60532 KB Output is correct
52 Correct 539 ms 72052 KB Output is correct
53 Correct 476 ms 68488 KB Output is correct
54 Correct 92 ms 29288 KB Output is correct
55 Correct 189 ms 41208 KB Output is correct
56 Correct 399 ms 53340 KB Output is correct
57 Correct 165 ms 57492 KB Output is correct
58 Correct 192 ms 57228 KB Output is correct
59 Correct 190 ms 47948 KB Output is correct
60 Correct 111 ms 31644 KB Output is correct
61 Correct 179 ms 39164 KB Output is correct
62 Correct 434 ms 66404 KB Output is correct
63 Correct 279 ms 56900 KB Output is correct
64 Correct 396 ms 60424 KB Output is correct
65 Correct 519 ms 52652 KB Output is correct
66 Correct 796 ms 77728 KB Output is correct
67 Correct 818 ms 77600 KB Output is correct
68 Correct 666 ms 72536 KB Output is correct
69 Correct 636 ms 67952 KB Output is correct
70 Correct 99 ms 30368 KB Output is correct
71 Correct 699 ms 77732 KB Output is correct
72 Correct 778 ms 77728 KB Output is correct
73 Correct 647 ms 72420 KB Output is correct
74 Correct 792 ms 76064 KB Output is correct
75 Correct 681 ms 77752 KB Output is correct
76 Correct 678 ms 77592 KB Output is correct
77 Correct 601 ms 72508 KB Output is correct
78 Correct 652 ms 69192 KB Output is correct
79 Correct 855 ms 74664 KB Output is correct
80 Correct 943 ms 71068 KB Output is correct
81 Correct 349 ms 32356 KB Output is correct
82 Correct 516 ms 43872 KB Output is correct
83 Correct 683 ms 55940 KB Output is correct
84 Correct 733 ms 60116 KB Output is correct
85 Correct 584 ms 59976 KB Output is correct
86 Correct 500 ms 50804 KB Output is correct
87 Correct 287 ms 34300 KB Output is correct
88 Correct 368 ms 41680 KB Output is correct
89 Correct 632 ms 69024 KB Output is correct
90 Correct 630 ms 59416 KB Output is correct
91 Correct 588 ms 63096 KB Output is correct