oj.uz

Submission #732420

# Submission time Handle Problem Language Result Execution time Memory
732420 2023-04-29T04:00:57 Z SanguineChameleon Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 390 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) {
	if (lx < min_X && max_X < rx && ly < min_Y && max_Y < ry) {
		return 1;
	}
	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);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 198 ms 27524 KB Output is correct
4 Correct 269 ms 36796 KB Output is correct
5 Correct 237 ms 36504 KB Output is correct
6 Correct 215 ms 30648 KB Output is correct
7 Correct 215 ms 29896 KB Output is correct
8 Correct 87 ms 13368 KB Output is correct
9 Correct 233 ms 36620 KB Output is correct
10 Correct 227 ms 36284 KB Output is correct
11 Correct 236 ms 30644 KB Output is correct
12 Correct 250 ms 36264 KB Output is correct
13 Correct 222 ms 36760 KB Output is correct
14 Correct 213 ms 36364 KB Output is correct
15 Correct 189 ms 30620 KB Output is correct
16 Correct 196 ms 28624 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 390 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -