oj.uz

Submission #129056

# Submission time Handle Problem Language Result Execution time Memory
129056 2019-07-11T13:52:04 Z keko37 Land of the Rainbow Gold (APIO17_rainbow) C++14
50 / 100
 812 ms 182980 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 * 320], rig[MAXN * 320], t[MAXN * 320];
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 < m+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 21 ms 19320 KB Output is correct
2 Correct 22 ms 19704 KB Output is correct
3 Correct 21 ms 19448 KB Output is correct
4 Correct 20 ms 19320 KB Output is correct
5 Correct 21 ms 19704 KB Output is correct
6 Correct 19 ms 19196 KB Output is correct
7 Correct 19 ms 19192 KB Output is correct
8 Correct 20 ms 19188 KB Output is correct
9 Correct 19 ms 19132 KB Output is correct
10 Correct 22 ms 19124 KB Output is correct
11 Correct 21 ms 19324 KB Output is correct
12 Correct 26 ms 19576 KB Output is correct
13 Correct 26 ms 19832 KB Output is correct
14 Correct 58 ms 20088 KB Output is correct
15 Correct 19 ms 19192 KB Output is correct
16 Correct 19 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 19 ms 19192 KB Output is correct
2 Correct 19 ms 19192 KB Output is correct
3 Correct 651 ms 123596 KB Output is correct
4 Correct 769 ms 179892 KB Output is correct
5 Correct 772 ms 178428 KB Output is correct
6 Correct 645 ms 146832 KB Output is correct
7 Correct 720 ms 144468 KB Output is correct
8 Correct 397 ms 40712 KB Output is correct
9 Correct 807 ms 179936 KB Output is correct
10 Correct 812 ms 178380 KB Output is correct
11 Correct 693 ms 146836 KB Output is correct
12 Correct 380 ms 169948 KB Output is correct
13 Correct 395 ms 179604 KB Output is correct
14 Correct 409 ms 178284 KB Output is correct
15 Correct 348 ms 146800 KB Output is correct
16 Correct 641 ms 139048 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19192 KB Output is correct
2 Correct 292 ms 178724 KB Output is correct
3 Correct 297 ms 182980 KB Output is correct
4 Correct 297 ms 179824 KB Output is correct
5 Correct 240 ms 146064 KB Output is correct
6 Correct 103 ms 65660 KB Output is correct
7 Correct 148 ms 91740 KB Output is correct
8 Correct 237 ms 135148 KB Output is correct
9 Correct 201 ms 114912 KB Output is correct
10 Incorrect 59 ms 38596 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19320 KB Output is correct
2 Correct 22 ms 19704 KB Output is correct
3 Correct 21 ms 19448 KB Output is correct
4 Correct 20 ms 19320 KB Output is correct
5 Correct 21 ms 19704 KB Output is correct
6 Correct 19 ms 19196 KB Output is correct
7 Correct 19 ms 19192 KB Output is correct
8 Correct 20 ms 19188 KB Output is correct
9 Correct 19 ms 19132 KB Output is correct
10 Correct 22 ms 19124 KB Output is correct
11 Correct 21 ms 19324 KB Output is correct
12 Correct 26 ms 19576 KB Output is correct
13 Correct 26 ms 19832 KB Output is correct
14 Correct 58 ms 20088 KB Output is correct
15 Correct 19 ms 19192 KB Output is correct
16 Correct 19 ms 19192 KB Output is correct
17 Correct 19 ms 19192 KB Output is correct
18 Correct 709 ms 64764 KB Output is correct
19 Correct 259 ms 24568 KB Output is correct
20 Correct 181 ms 22856 KB Output is correct
21 Correct 203 ms 23296 KB Output is correct
22 Correct 230 ms 23672 KB Output is correct
23 Correct 256 ms 24496 KB Output is correct
24 Correct 184 ms 23032 KB Output is correct
25 Correct 208 ms 23368 KB Output is correct
26 Correct 232 ms 23744 KB Output is correct
27 Correct 381 ms 57340 KB Output is correct
28 Correct 328 ms 39788 KB Output is correct
29 Correct 378 ms 54828 KB Output is correct
30 Correct 552 ms 104696 KB Output is correct
31 Correct 22 ms 19320 KB Output is correct
32 Correct 578 ms 57444 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19320 KB Output is correct
2 Correct 22 ms 19704 KB Output is correct
3 Correct 21 ms 19448 KB Output is correct
4 Correct 20 ms 19320 KB Output is correct
5 Correct 21 ms 19704 KB Output is correct
6 Correct 19 ms 19196 KB Output is correct
7 Correct 19 ms 19192 KB Output is correct
8 Correct 20 ms 19188 KB Output is correct
9 Correct 19 ms 19132 KB Output is correct
10 Correct 22 ms 19124 KB Output is correct
11 Correct 21 ms 19324 KB Output is correct
12 Correct 26 ms 19576 KB Output is correct
13 Correct 26 ms 19832 KB Output is correct
14 Correct 58 ms 20088 KB Output is correct
15 Correct 19 ms 19192 KB Output is correct
16 Correct 19 ms 19192 KB Output is correct
17 Correct 19 ms 19192 KB Output is correct
18 Correct 709 ms 64764 KB Output is correct
19 Correct 259 ms 24568 KB Output is correct
20 Correct 181 ms 22856 KB Output is correct
21 Correct 203 ms 23296 KB Output is correct
22 Correct 230 ms 23672 KB Output is correct
23 Correct 256 ms 24496 KB Output is correct
24 Correct 184 ms 23032 KB Output is correct
25 Correct 208 ms 23368 KB Output is correct
26 Correct 232 ms 23744 KB Output is correct
27 Correct 381 ms 57340 KB Output is correct
28 Correct 328 ms 39788 KB Output is correct
29 Correct 378 ms 54828 KB Output is correct
30 Correct 552 ms 104696 KB Output is correct
31 Correct 22 ms 19320 KB Output is correct
32 Correct 578 ms 57444 KB Output is correct
33 Correct 292 ms 178724 KB Output is correct
34 Correct 297 ms 182980 KB Output is correct
35 Correct 297 ms 179824 KB Output is correct
36 Correct 240 ms 146064 KB Output is correct
37 Correct 103 ms 65660 KB Output is correct
38 Correct 148 ms 91740 KB Output is correct
39 Correct 237 ms 135148 KB Output is correct
40 Correct 201 ms 114912 KB Output is correct
41 Incorrect 59 ms 38596 KB Output isn't correct
42 Halted 0 ms 0 KB -