oj.uz

Submission #732438

# Submission time Handle Problem Language Result Execution time Memory
732438 2023-04-29T04:21:41 Z SanguineChameleon Land of the Rainbow Gold (APIO17_rainbow) C++17
50 / 100
 377 ms 1048576 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

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

	void init(int _R, int _C) {
		R = _R;
		C = _C;
		a.resize(R + 1);
		for (int i = 0; i <= R; i++) {
			a[i].resize(C + 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});
		a[x][y]++;
	}

	void build() {
		for (int i = 1; i <= R; i++) {
			for (int j = 1; j <= C; j++) {
				a[i][j] += a[i][j - 1];
			}
		}
		for (int j = 1; j <= C; j++) {
			for (int i = 1; i <= R; i++) {
				a[i][j] += a[i - 1][j];
			}
		}
	}

	int get(int x, int y) {
		return a[x][y];
	}

	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 3 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 5 ms 724 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 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 0 ms 212 KB Output is correct
3 Correct 181 ms 24776 KB Output is correct
4 Correct 228 ms 33864 KB Output is correct
5 Correct 220 ms 33492 KB Output is correct
6 Correct 209 ms 27796 KB Output is correct
7 Correct 218 ms 26916 KB Output is correct
8 Correct 80 ms 10444 KB Output is correct
9 Correct 218 ms 33832 KB Output is correct
10 Correct 221 ms 33460 KB Output is correct
11 Correct 207 ms 27732 KB Output is correct
12 Correct 243 ms 33192 KB Output is correct
13 Correct 213 ms 33932 KB Output is correct
14 Correct 213 ms 33612 KB Output is correct
15 Correct 199 ms 27756 KB Output is correct
16 Correct 185 ms 25756 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 377 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 5 ms 724 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 228 ms 33752 KB Output is correct
19 Correct 63 ms 5936 KB Output is correct
20 Correct 52 ms 3916 KB Output is correct
21 Correct 53 ms 4540 KB Output is correct
22 Correct 57 ms 5644 KB Output is correct
23 Correct 52 ms 5820 KB Output is correct
24 Correct 52 ms 4068 KB Output is correct
25 Correct 55 ms 4688 KB Output is correct
26 Correct 60 ms 5708 KB Output is correct
27 Correct 221 ms 31212 KB Output is correct
28 Correct 194 ms 25208 KB Output is correct
29 Correct 234 ms 30344 KB Output is correct
30 Correct 323 ms 47820 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 200 ms 31284 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 3 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 5 ms 724 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 228 ms 33752 KB Output is correct
19 Correct 63 ms 5936 KB Output is correct
20 Correct 52 ms 3916 KB Output is correct
21 Correct 53 ms 4540 KB Output is correct
22 Correct 57 ms 5644 KB Output is correct
23 Correct 52 ms 5820 KB Output is correct
24 Correct 52 ms 4068 KB Output is correct
25 Correct 55 ms 4688 KB Output is correct
26 Correct 60 ms 5708 KB Output is correct
27 Correct 221 ms 31212 KB Output is correct
28 Correct 194 ms 25208 KB Output is correct
29 Correct 234 ms 30344 KB Output is correct
30 Correct 323 ms 47820 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 200 ms 31284 KB Output is correct
33 Runtime error 377 ms 1048576 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -