oj.uz

Submission #129062

# Submission time Handle Problem Language Result Execution time Memory
129062 2019-07-11T14:17:38 Z keko37 Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 1172 ms 186724 KB 
#include <bits/stdc++.h>
#include "rainbow.h"

using namespace std;

const int MAXN = 200005;

int n, m, len, ofs, cnt, xmn, xmx, ymn, ymx;
vector <int> ff[MAXN], vv[MAXN], ex[MAXN], ey[MAXN];
int lef[MAXN * 80], rig[MAXN * 80], t[MAXN * 80];
int ffr[MAXN], vvr[MAXN], exr[MAXN], eyr[MAXN];

void ispis (int x, int d) {
	if (x == 0) return;
	for (int i=0; i<d; i++) cout << ' ';
	cout << x << " " << t[x] << endl;
	ispis(lef[x], d + 1);
	ispis(rig[x], d + 1);
}

void obradi () {
	for (int i=0; i<n; i++) {
		sort(ff[i].begin(), ff[i].end());
		ff[i].erase(unique(ff[i].begin(), ff[i].end()), ff[i].end());
		for (auto j : ff[i]) {
			vv[i].push_back(j); vv[i].push_back(j+1);
			vv[i+1].push_back(j); vv[i+1].push_back(j+1);
			ex[i].push_back(j); ex[i+1].push_back(j);
			ey[j].push_back(i); ey[j+1].push_back(i);
		}
	}
	for (int i=0; i<=n; i++) {
		sort(vv[i].begin(), vv[i].end());
		vv[i].erase(unique(vv[i].begin(), vv[i].end()), vv[i].end());
		sort(ex[i].begin(), ex[i].end());
		ex[i].erase(unique(ex[i].begin(), ex[i].end()), ex[i].end());
	}
	for (int i=0; i<=m; i++) {
		sort(ey[i].begin(), ey[i].end());
		ey[i].erase(unique(ey[i].begin(), ey[i].end()), ey[i].end());
	}
}

int build (int len) {
	int curr = ++cnt;
	if (len == 1) return curr;
	lef[curr] = build(len/2);
	rig[curr] = build(len/2);
	return curr;
}

int update (int x, int pos, int lo, int hi) {
	int curr = ++cnt;
	if (lo == hi) {
		t[curr] = t[x] + 1;
		return curr;
	}
	int mid = (lo + hi) / 2;
	if (pos <= mid) {
		lef[curr] = update(lef[x], pos, lo, mid);
		rig[curr] = rig[x];
	} else {
		lef[curr] = lef[x];
		rig[curr] = update(rig[x], pos, mid+1, hi);
	}
	t[curr] = t[lef[curr]] + t[rig[curr]];
	return curr;
}

int upit (int x, int from, int to, int lo, int hi) {
	if (from <= lo && hi <= to) return t[x];
	if (to < lo || hi < from) return 0;
	return upit(lef[x], from, to, lo, (lo + hi)/2) + upit(rig[x], from, to, (lo + hi)/2+1, hi);
}

void tour_init () {
	ofs = 1;
	while (ofs < max(m+1, n+1)) ofs *= 2;
	ffr[0] = build(ofs); vvr[0] = build(ofs);
	exr[0] = build(ofs); eyr[0] = build(ofs);
	for (int i=0; i<n; i++) {
		if (i > 0) ffr[i] = ffr[i-1];
		for (auto j : ff[i]) {
			ffr[i] = update(ffr[i], j, 0, ofs-1);
		}
	}
	for (int i=0; i<=n; i++) {
		if (i > 0) vvr[i] = vvr[i-1];
		for (auto j : vv[i]) {
			vvr[i] = update(vvr[i], j, 0, ofs-1);
		}
		if (i > 0) exr[i] = exr[i-1];
		for (auto j : ex[i]) {
			exr[i] = update(exr[i], j, 0, ofs-1);
		}
	}
	for (int i=0; i<=m; i++) {
		if (i > 0) eyr[i] = eyr[i-1];
		for (auto j : ey[i]) {
			eyr[i] = update(eyr[i], j, 0, ofs-1);
		}
	}
}

void init (int R, int C, int sx, int sy, int M, char *S) {
	n = R; m = C; len = M;
	sx--; sy--;
	xmn = xmx = sx;
	ymn = ymx = sy;
	ff[sx].push_back(sy);
	for (int i=0; i<len; i++) {
		if (S[i] == 'N') sx--;
		if (S[i] == 'E') sy++;
		if (S[i] == 'S') sx++;
		if (S[i] == 'W') sy--;
		xmn = min(xmn, sx); xmx = max(xmx, sx);
		ymn = min(ymn, sy); ymx = max(ymx, sy);
		ff[sx].push_back(sy);
	}
	obradi();
	tour_init();
}

int colour (int x1, int y1, int x2, int y2) {
	x1--; y1--; x2--; y2--;
	int f = 0, v = 0, e = 0;
	f = upit(ffr[x2], y1, y2, 0, ofs-1) - (x1 == 0 ? 0 : upit(ffr[x1-1], y1, y2, 0, ofs-1));
	if (x1 < x2 && y1 < y2) v = upit(vvr[x2], y1+1, y2, 0, ofs-1) - upit(vvr[x1], y1+1, y2, 0, ofs-1);
	if (x1 < x2) e += upit(exr[x2], y1, y2, 0, ofs-1) - upit(exr[x1], y1, y2, 0, ofs-1);
	if (y1 < y2) e += upit(eyr[y2], x1, x2, 0, ofs-1) - upit(eyr[y1], x1, x2, 0, ofs-1);
    return e + 1 - v - f + (x1 < xmn && xmx < x2 && y1 < ymn && ymx < y2);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19192 KB Output is correct
2 Correct 21 ms 19576 KB Output is correct
3 Correct 21 ms 19320 KB Output is correct
4 Correct 21 ms 19400 KB Output is correct
5 Correct 22 ms 19832 KB Output is correct
6 Correct 19 ms 19192 KB Output is correct
7 Correct 19 ms 19192 KB Output is correct
8 Correct 19 ms 19176 KB Output is correct
9 Correct 19 ms 19160 KB Output is correct
10 Correct 19 ms 19192 KB Output is correct
11 Correct 21 ms 19420 KB Output is correct
12 Correct 22 ms 19576 KB Output is correct
13 Correct 22 ms 19832 KB Output is correct
14 Correct 23 ms 20088 KB Output is correct
15 Correct 24 ms 19192 KB Output is correct
16 Correct 24 ms 19192 KB Output is correct
17 Correct 19 ms 19192 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 19192 KB Output is correct
2 Correct 19 ms 19192 KB Output is correct
3 Correct 652 ms 121064 KB Output is correct
4 Correct 756 ms 177416 KB Output is correct
5 Correct 763 ms 176200 KB Output is correct
6 Correct 637 ms 144352 KB Output is correct
7 Correct 681 ms 142188 KB Output is correct
8 Correct 386 ms 38360 KB Output is correct
9 Correct 803 ms 177416 KB Output is correct
10 Correct 795 ms 176132 KB Output is correct
11 Correct 696 ms 144336 KB Output is correct
12 Correct 375 ms 167656 KB Output is correct
13 Correct 391 ms 177348 KB Output is correct
14 Correct 395 ms 176016 KB Output is correct
15 Correct 343 ms 144624 KB Output is correct
16 Correct 624 ms 136616 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 19192 KB Output is correct
2 Correct 290 ms 178668 KB Output is correct
3 Correct 301 ms 182972 KB Output is correct
4 Correct 292 ms 179876 KB Output is correct
5 Correct 237 ms 145908 KB Output is correct
6 Correct 103 ms 65736 KB Output is correct
7 Correct 156 ms 91640 KB Output is correct
8 Correct 238 ms 135128 KB Output is correct
9 Correct 199 ms 114844 KB Output is correct
10 Correct 84 ms 55032 KB Output is correct
11 Correct 151 ms 93940 KB Output is correct
12 Correct 291 ms 178648 KB Output is correct
13 Correct 311 ms 183060 KB Output is correct
14 Correct 299 ms 179932 KB Output is correct
15 Correct 236 ms 145996 KB Output is correct
16 Correct 94 ms 60320 KB Output is correct
17 Correct 147 ms 91796 KB Output is correct
18 Correct 280 ms 177052 KB Output is correct
19 Correct 288 ms 180844 KB Output is correct
20 Correct 296 ms 180844 KB Output is correct
21 Correct 275 ms 135144 KB Output is correct
22 Correct 205 ms 114860 KB Output is correct
23 Correct 84 ms 55028 KB Output is correct
24 Correct 154 ms 93972 KB Output is correct
25 Correct 300 ms 178664 KB Output is correct
26 Correct 295 ms 182912 KB Output is correct
27 Correct 297 ms 179836 KB Output is correct
28 Correct 237 ms 146028 KB Output is correct
29 Correct 94 ms 60408 KB Output is correct
30 Correct 146 ms 91792 KB Output is correct
31 Correct 282 ms 177016 KB Output is correct
32 Correct 290 ms 180716 KB Output is correct
33 Correct 291 ms 180844 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19192 KB Output is correct
2 Correct 21 ms 19576 KB Output is correct
3 Correct 21 ms 19320 KB Output is correct
4 Correct 21 ms 19400 KB Output is correct
5 Correct 22 ms 19832 KB Output is correct
6 Correct 19 ms 19192 KB Output is correct
7 Correct 19 ms 19192 KB Output is correct
8 Correct 19 ms 19176 KB Output is correct
9 Correct 19 ms 19160 KB Output is correct
10 Correct 19 ms 19192 KB Output is correct
11 Correct 21 ms 19420 KB Output is correct
12 Correct 22 ms 19576 KB Output is correct
13 Correct 22 ms 19832 KB Output is correct
14 Correct 23 ms 20088 KB Output is correct
15 Correct 24 ms 19192 KB Output is correct
16 Correct 24 ms 19192 KB Output is correct
17 Correct 19 ms 19192 KB Output is correct
18 Correct 738 ms 62416 KB Output is correct
19 Correct 253 ms 22264 KB Output is correct
20 Correct 180 ms 20700 KB Output is correct
21 Correct 202 ms 20936 KB Output is correct
22 Correct 223 ms 21368 KB Output is correct
23 Correct 251 ms 22392 KB Output is correct
24 Correct 182 ms 20872 KB Output is correct
25 Correct 212 ms 21180 KB Output is correct
26 Correct 227 ms 21496 KB Output is correct
27 Correct 377 ms 55032 KB Output is correct
28 Correct 320 ms 37464 KB Output is correct
29 Correct 382 ms 52444 KB Output is correct
30 Correct 557 ms 102520 KB Output is correct
31 Correct 23 ms 19320 KB Output is correct
32 Correct 634 ms 55160 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19192 KB Output is correct
2 Correct 21 ms 19576 KB Output is correct
3 Correct 21 ms 19320 KB Output is correct
4 Correct 21 ms 19400 KB Output is correct
5 Correct 22 ms 19832 KB Output is correct
6 Correct 19 ms 19192 KB Output is correct
7 Correct 19 ms 19192 KB Output is correct
8 Correct 19 ms 19176 KB Output is correct
9 Correct 19 ms 19160 KB Output is correct
10 Correct 19 ms 19192 KB Output is correct
11 Correct 21 ms 19420 KB Output is correct
12 Correct 22 ms 19576 KB Output is correct
13 Correct 22 ms 19832 KB Output is correct
14 Correct 23 ms 20088 KB Output is correct
15 Correct 24 ms 19192 KB Output is correct
16 Correct 24 ms 19192 KB Output is correct
17 Correct 19 ms 19192 KB Output is correct
18 Correct 738 ms 62416 KB Output is correct
19 Correct 253 ms 22264 KB Output is correct
20 Correct 180 ms 20700 KB Output is correct
21 Correct 202 ms 20936 KB Output is correct
22 Correct 223 ms 21368 KB Output is correct
23 Correct 251 ms 22392 KB Output is correct
24 Correct 182 ms 20872 KB Output is correct
25 Correct 212 ms 21180 KB Output is correct
26 Correct 227 ms 21496 KB Output is correct
27 Correct 377 ms 55032 KB Output is correct
28 Correct 320 ms 37464 KB Output is correct
29 Correct 382 ms 52444 KB Output is correct
30 Correct 557 ms 102520 KB Output is correct
31 Correct 23 ms 19320 KB Output is correct
32 Correct 634 ms 55160 KB Output is correct
33 Correct 290 ms 178668 KB Output is correct
34 Correct 301 ms 182972 KB Output is correct
35 Correct 292 ms 179876 KB Output is correct
36 Correct 237 ms 145908 KB Output is correct
37 Correct 103 ms 65736 KB Output is correct
38 Correct 156 ms 91640 KB Output is correct
39 Correct 238 ms 135128 KB Output is correct
40 Correct 199 ms 114844 KB Output is correct
41 Correct 84 ms 55032 KB Output is correct
42 Correct 151 ms 93940 KB Output is correct
43 Correct 291 ms 178648 KB Output is correct
44 Correct 311 ms 183060 KB Output is correct
45 Correct 299 ms 179932 KB Output is correct
46 Correct 236 ms 145996 KB Output is correct
47 Correct 94 ms 60320 KB Output is correct
48 Correct 147 ms 91796 KB Output is correct
49 Correct 280 ms 177052 KB Output is correct
50 Correct 288 ms 180844 KB Output is correct
51 Correct 296 ms 180844 KB Output is correct
52 Correct 275 ms 135144 KB Output is correct
53 Correct 205 ms 114860 KB Output is correct
54 Correct 84 ms 55028 KB Output is correct
55 Correct 154 ms 93972 KB Output is correct
56 Correct 300 ms 178664 KB Output is correct
57 Correct 295 ms 182912 KB Output is correct
58 Correct 297 ms 179836 KB Output is correct
59 Correct 237 ms 146028 KB Output is correct
60 Correct 94 ms 60408 KB Output is correct
61 Correct 146 ms 91792 KB Output is correct
62 Correct 282 ms 177016 KB Output is correct
63 Correct 290 ms 180716 KB Output is correct
64 Correct 291 ms 180844 KB Output is correct
65 Correct 1018 ms 138824 KB Output is correct
66 Correct 1048 ms 118384 KB Output is correct
67 Correct 544 ms 58600 KB Output is correct
68 Correct 711 ms 97608 KB Output is correct
69 Correct 1172 ms 182248 KB Output is correct
70 Correct 1097 ms 186724 KB Output is correct
71 Correct 1054 ms 183236 KB Output is correct
72 Correct 1035 ms 149524 KB Output is correct
73 Correct 845 ms 63944 KB Output is correct
74 Correct 852 ms 95224 KB Output is correct
75 Correct 1000 ms 180620 KB Output is correct
76 Correct 1162 ms 184216 KB Output is correct
77 Correct 928 ms 184128 KB Output is correct
78 Correct 652 ms 121064 KB Output is correct
79 Correct 756 ms 177416 KB Output is correct
80 Correct 763 ms 176200 KB Output is correct
81 Correct 637 ms 144352 KB Output is correct
82 Correct 681 ms 142188 KB Output is correct
83 Correct 386 ms 38360 KB Output is correct
84 Correct 803 ms 177416 KB Output is correct
85 Correct 795 ms 176132 KB Output is correct
86 Correct 696 ms 144336 KB Output is correct
87 Correct 375 ms 167656 KB Output is correct
88 Correct 391 ms 177348 KB Output is correct
89 Correct 395 ms 176016 KB Output is correct
90 Correct 343 ms 144624 KB Output is correct
91 Correct 624 ms 136616 KB Output is correct