oj.uz

Submission #732441

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

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

	void init(int _R, int _C) {
		R = _R;
		C = _C;
		bit.resize(R + 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});
	}

	void update(int x, int y) {
		for (int i = x; i <= R; i += i & (-i)) {
			for (int j = y; j <= C; j += j & (-j)) {
				bit[i][j]++;
			}
		}
	}

	void build() {
		for (auto p: S) {
			int x = p.first;
			int y = p.second;
			update(x, y);
		}
	}

	int get(int x, int y) {
		int res = 0;
		for (int i = x; i > 0; i -= i & (-i)) {
			for (int j = y; j > 0; j -= j & (-j)) {
				auto it = bit[i].find(j);
				if (it != bit[i].end()) {
					res += it->second;
				}
			}
		}
		return res;
	}

	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 3 ms 340 KB Output is correct
2 Correct 7 ms 852 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 8 ms 852 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 6 ms 724 KB Output is correct
13 Correct 8 ms 1096 KB Output is correct
14 Correct 9 ms 1228 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1105 ms 34572 KB Output is correct
4 Correct 1853 ms 57060 KB Output is correct
5 Correct 1677 ms 54888 KB Output is correct
6 Correct 1096 ms 36852 KB Output is correct
7 Correct 1264 ms 36392 KB Output is correct
8 Correct 104 ms 976 KB Output is correct
9 Correct 1820 ms 57160 KB Output is correct
10 Correct 1731 ms 54968 KB Output is correct
11 Correct 1245 ms 36992 KB Output is correct
12 Correct 731 ms 53448 KB Output is correct
13 Correct 718 ms 57128 KB Output is correct
14 Correct 724 ms 54976 KB Output is correct
15 Correct 564 ms 37144 KB Output is correct
16 Correct 1349 ms 41096 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 3066 ms 225820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 7 ms 852 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 8 ms 852 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 6 ms 724 KB Output is correct
13 Correct 8 ms 1096 KB Output is correct
14 Correct 9 ms 1228 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Execution timed out 3038 ms 48192 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 7 ms 852 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 8 ms 852 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 6 ms 724 KB Output is correct
13 Correct 8 ms 1096 KB Output is correct
14 Correct 9 ms 1228 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Execution timed out 3038 ms 48192 KB Time limit exceeded
19 Halted 0 ms 0 KB -