oj.uz

Submission #162094

# Submission time Handle Problem Language Result Execution time Memory
162094 2019-11-06T10:56:24 Z Minnakhmetov Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 2008 ms 173996 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;

#define all(aaa) aaa.begin(), aaa.end()

const int N = 2e5 + 5;

struct ST {
	vector<pair<int, int>> pts;
	vector<int> t[N * 4];

	void init() {
		if (!pts.empty()) {
			sort(all(pts));
			pts.erase(unique(all(pts)), pts.end());
			build(1, 0, (int)pts.size() - 1);	
		}
	}

	void build(int v, int L, int R) {
		if (L == R) {
			t[v] = {pts[L].second};
		}
		else {
			int m = (L + R) >> 1;
			build(v * 2, L, m);
			build(v * 2 + 1, m + 1, R);
			merge(all(t[v * 2]), all(t[v * 2 + 1]), back_inserter(t[v]));
		}
	}

	int que(int lx, int rx, int ly, int ry, int v, int L, int R) {
		if (rx < pts[L].first || lx > pts[R].first)
			return 0;
		if (lx <= pts[L].first && pts[R].first <= rx) {
			return upper_bound(all(t[v]), ry) - lower_bound(all(t[v]), ly);
		}
		int m = (L + R) >> 1;
		return que(lx, rx, ly, ry, v * 2, L, m)
			+ que(lx, rx, ly, ry, v * 2 + 1, m + 1, R);
	}

	int que(int lx, int rx, int ly, int ry) {
		if (pts.empty())
			return 0;
		return que(lx, rx, ly, ry, 1, 0, pts.size() - 1);
	}

} teh, tev, tf, tv;

string dir = "NSEW";
const int dx[4] = {-1, 1, 0, 0},
		  dy[4] = {0, 0, 1, -1},
		  sdx[4] = {1, 1, 0, 0},
		  sdy[4] = {0, 1, 0, 1};

int mnx, mny, mxx, mxy;
set<pair<int, int>> st;

void init(int R, int C, int sr, int sc, int M, char *S) {
	mnx = sr;
	mxx = sr;
	mny = sc;
	mxy = sc;

	int x = sr, y = sc;
	st.insert({x, y});

	for (int i = 0; i < M; i++) {
		int k = find(all(dir), S[i]) - dir.begin();
		x += dx[k];
		y += dy[k];
		st.insert({x, y});

		mnx = min(mnx, x);
		mxx = max(mxx, x);
		mny = min(mny, y);
		mxy = max(mxy, y);
	}

	for (auto p : st) {
		tf.pts.push_back(p);
		tev.pts.push_back({p.first, p.second});
		tev.pts.push_back({p.first - 1, p.second});
		teh.pts.push_back({p.first, p.second});
		teh.pts.push_back({p.first, p.second - 1});

		for (int i = 0; i < 4; i++) {
			tv.pts.push_back({p.first - sdx[i], p.second - sdy[i]});
		}
	}

	tev.init();
	teh.init();
	tv.init();
	tf.init();
}

int colour(int ar, int ac, int br, int bc) {
	int ans = 1;

	if (ar < mnx && mxx < br &&
		ac < mny && mxy < bc) {
		ans++;
	}

	ans += tev.que(ar, br - 1, ac, bc);
	ans += teh.que(ar, br, ac, bc - 1);
	ans -= tv.que(ar, br - 1, ac, bc - 1);
	ans -= tf.que(ar, br, ac, bc);

	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 75640 KB Output is correct
2 Correct 80 ms 76152 KB Output is correct
3 Correct 76 ms 75612 KB Output is correct
4 Correct 76 ms 75768 KB Output is correct
5 Correct 80 ms 76280 KB Output is correct
6 Correct 73 ms 75544 KB Output is correct
7 Correct 75 ms 75496 KB Output is correct
8 Correct 72 ms 75648 KB Output is correct
9 Correct 74 ms 75512 KB Output is correct
10 Correct 73 ms 75484 KB Output is correct
11 Correct 77 ms 75888 KB Output is correct
12 Correct 79 ms 75996 KB Output is correct
13 Correct 101 ms 76536 KB Output is correct
14 Correct 93 ms 76792 KB Output is correct
15 Correct 84 ms 75512 KB Output is correct
16 Correct 81 ms 75640 KB Output is correct
17 Correct 79 ms 75512 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 75640 KB Output is correct
2 Correct 79 ms 75512 KB Output is correct
3 Correct 513 ms 127516 KB Output is correct
4 Correct 743 ms 170984 KB Output is correct
5 Correct 731 ms 170560 KB Output is correct
6 Correct 595 ms 154620 KB Output is correct
7 Correct 616 ms 149316 KB Output is correct
8 Correct 156 ms 79340 KB Output is correct
9 Correct 720 ms 170804 KB Output is correct
10 Correct 735 ms 170536 KB Output is correct
11 Correct 635 ms 154768 KB Output is correct
12 Correct 592 ms 166340 KB Output is correct
13 Correct 572 ms 170880 KB Output is correct
14 Correct 597 ms 170452 KB Output is correct
15 Correct 551 ms 154824 KB Output is correct
16 Correct 566 ms 150592 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 75512 KB Output is correct
2 Correct 449 ms 167428 KB Output is correct
3 Correct 445 ms 167612 KB Output is correct
4 Correct 458 ms 171888 KB Output is correct
5 Correct 346 ms 145736 KB Output is correct
6 Correct 152 ms 91864 KB Output is correct
7 Correct 228 ms 108860 KB Output is correct
8 Correct 426 ms 160456 KB Output is correct
9 Correct 382 ms 153212 KB Output is correct
10 Correct 156 ms 94284 KB Output is correct
11 Correct 264 ms 121472 KB Output is correct
12 Correct 470 ms 167656 KB Output is correct
13 Correct 451 ms 167428 KB Output is correct
14 Correct 449 ms 171944 KB Output is correct
15 Correct 351 ms 145860 KB Output is correct
16 Correct 141 ms 89824 KB Output is correct
17 Correct 225 ms 108896 KB Output is correct
18 Correct 490 ms 172036 KB Output is correct
19 Correct 462 ms 171908 KB Output is correct
20 Correct 457 ms 171920 KB Output is correct
21 Correct 421 ms 160452 KB Output is correct
22 Correct 389 ms 153420 KB Output is correct
23 Correct 150 ms 94176 KB Output is correct
24 Correct 261 ms 121456 KB Output is correct
25 Correct 494 ms 167640 KB Output is correct
26 Correct 434 ms 167428 KB Output is correct
27 Correct 451 ms 171904 KB Output is correct
28 Correct 346 ms 145732 KB Output is correct
29 Correct 146 ms 89696 KB Output is correct
30 Correct 240 ms 108932 KB Output is correct
31 Correct 455 ms 172032 KB Output is correct
32 Correct 460 ms 171780 KB Output is correct
33 Correct 467 ms 171804 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 75640 KB Output is correct
2 Correct 80 ms 76152 KB Output is correct
3 Correct 76 ms 75612 KB Output is correct
4 Correct 76 ms 75768 KB Output is correct
5 Correct 80 ms 76280 KB Output is correct
6 Correct 73 ms 75544 KB Output is correct
7 Correct 75 ms 75496 KB Output is correct
8 Correct 72 ms 75648 KB Output is correct
9 Correct 74 ms 75512 KB Output is correct
10 Correct 73 ms 75484 KB Output is correct
11 Correct 77 ms 75888 KB Output is correct
12 Correct 79 ms 75996 KB Output is correct
13 Correct 101 ms 76536 KB Output is correct
14 Correct 93 ms 76792 KB Output is correct
15 Correct 84 ms 75512 KB Output is correct
16 Correct 81 ms 75640 KB Output is correct
17 Correct 79 ms 75512 KB Output is correct
18 Correct 2008 ms 123404 KB Output is correct
19 Correct 372 ms 79864 KB Output is correct
20 Correct 318 ms 77944 KB Output is correct
21 Correct 359 ms 78416 KB Output is correct
22 Correct 401 ms 78988 KB Output is correct
23 Correct 341 ms 79736 KB Output is correct
24 Correct 414 ms 78544 KB Output is correct
25 Correct 429 ms 78808 KB Output is correct
26 Correct 439 ms 79224 KB Output is correct
27 Correct 879 ms 117592 KB Output is correct
28 Correct 547 ms 94728 KB Output is correct
29 Correct 682 ms 110932 KB Output is correct
30 Correct 1425 ms 173996 KB Output is correct
31 Correct 77 ms 75628 KB Output is correct
32 Correct 1419 ms 117244 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 75640 KB Output is correct
2 Correct 80 ms 76152 KB Output is correct
3 Correct 76 ms 75612 KB Output is correct
4 Correct 76 ms 75768 KB Output is correct
5 Correct 80 ms 76280 KB Output is correct
6 Correct 73 ms 75544 KB Output is correct
7 Correct 75 ms 75496 KB Output is correct
8 Correct 72 ms 75648 KB Output is correct
9 Correct 74 ms 75512 KB Output is correct
10 Correct 73 ms 75484 KB Output is correct
11 Correct 77 ms 75888 KB Output is correct
12 Correct 79 ms 75996 KB Output is correct
13 Correct 101 ms 76536 KB Output is correct
14 Correct 93 ms 76792 KB Output is correct
15 Correct 84 ms 75512 KB Output is correct
16 Correct 81 ms 75640 KB Output is correct
17 Correct 79 ms 75512 KB Output is correct
18 Correct 2008 ms 123404 KB Output is correct
19 Correct 372 ms 79864 KB Output is correct
20 Correct 318 ms 77944 KB Output is correct
21 Correct 359 ms 78416 KB Output is correct
22 Correct 401 ms 78988 KB Output is correct
23 Correct 341 ms 79736 KB Output is correct
24 Correct 414 ms 78544 KB Output is correct
25 Correct 429 ms 78808 KB Output is correct
26 Correct 439 ms 79224 KB Output is correct
27 Correct 879 ms 117592 KB Output is correct
28 Correct 547 ms 94728 KB Output is correct
29 Correct 682 ms 110932 KB Output is correct
30 Correct 1425 ms 173996 KB Output is correct
31 Correct 77 ms 75628 KB Output is correct
32 Correct 1419 ms 117244 KB Output is correct
33 Correct 449 ms 167428 KB Output is correct
34 Correct 445 ms 167612 KB Output is correct
35 Correct 458 ms 171888 KB Output is correct
36 Correct 346 ms 145736 KB Output is correct
37 Correct 152 ms 91864 KB Output is correct
38 Correct 228 ms 108860 KB Output is correct
39 Correct 426 ms 160456 KB Output is correct
40 Correct 382 ms 153212 KB Output is correct
41 Correct 156 ms 94284 KB Output is correct
42 Correct 264 ms 121472 KB Output is correct
43 Correct 470 ms 167656 KB Output is correct
44 Correct 451 ms 167428 KB Output is correct
45 Correct 449 ms 171944 KB Output is correct
46 Correct 351 ms 145860 KB Output is correct
47 Correct 141 ms 89824 KB Output is correct
48 Correct 225 ms 108896 KB Output is correct
49 Correct 490 ms 172036 KB Output is correct
50 Correct 462 ms 171908 KB Output is correct
51 Correct 457 ms 171920 KB Output is correct
52 Correct 421 ms 160452 KB Output is correct
53 Correct 389 ms 153420 KB Output is correct
54 Correct 150 ms 94176 KB Output is correct
55 Correct 261 ms 121456 KB Output is correct
56 Correct 494 ms 167640 KB Output is correct
57 Correct 434 ms 167428 KB Output is correct
58 Correct 451 ms 171904 KB Output is correct
59 Correct 346 ms 145732 KB Output is correct
60 Correct 146 ms 89696 KB Output is correct
61 Correct 240 ms 108932 KB Output is correct
62 Correct 455 ms 172032 KB Output is correct
63 Correct 460 ms 171780 KB Output is correct
64 Correct 467 ms 171804 KB Output is correct
65 Correct 1081 ms 162472 KB Output is correct
66 Correct 1103 ms 155404 KB Output is correct
67 Correct 681 ms 96396 KB Output is correct
68 Correct 957 ms 123412 KB Output is correct
69 Correct 553 ms 169472 KB Output is correct
70 Correct 1107 ms 169244 KB Output is correct
71 Correct 741 ms 173516 KB Output is correct
72 Correct 656 ms 147656 KB Output is correct
73 Correct 229 ms 91224 KB Output is correct
74 Correct 310 ms 110420 KB Output is correct
75 Correct 535 ms 173380 KB Output is correct
76 Correct 918 ms 173472 KB Output is correct
77 Correct 982 ms 173532 KB Output is correct
78 Correct 513 ms 127516 KB Output is correct
79 Correct 743 ms 170984 KB Output is correct
80 Correct 731 ms 170560 KB Output is correct
81 Correct 595 ms 154620 KB Output is correct
82 Correct 616 ms 149316 KB Output is correct
83 Correct 156 ms 79340 KB Output is correct
84 Correct 720 ms 170804 KB Output is correct
85 Correct 735 ms 170536 KB Output is correct
86 Correct 635 ms 154768 KB Output is correct
87 Correct 592 ms 166340 KB Output is correct
88 Correct 572 ms 170880 KB Output is correct
89 Correct 597 ms 170452 KB Output is correct
90 Correct 551 ms 154824 KB Output is correct
91 Correct 566 ms 150592 KB Output is correct