oj.uz

Submission #561995

# Submission time Handle Problem Language Result Execution time Memory
561995 2022-05-14T03:43:18 Z hollwo_pelw Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 796 ms 77348 KB 
#include "rainbow.h"

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int min_X, min_Y, max_X, max_Y, tomap[1 << 8];

struct data_t {
	vector<pair<int, int>> list_val;
	vector<int> val[N];
	inline void pre_add(int x, int y) {
		x -= min_X - 1, y -= min_Y - 1;
		list_val.emplace_back(x, y);
	}

	inline void work() {
		sort(list_val.begin(), list_val.end());
		list_val.erase(unique(list_val.begin(), list_val.end()), list_val.end());

		for (auto [x, y] : list_val) {
			for (; x < N; x += x & -x)
				val[x].push_back(y);
		}

		for (int i = 1; i < N; i++)
			sort(val[i].begin(), val[i].end());
	}

	inline int count(int p, int l, int r) {
		int res = 0;
		for (p = min(p, N - 1); p > 0; p -= p & -p) {
			res += upper_bound(val[p].begin(), val[p].end(), r)
				 - lower_bound(val[p].begin(), val[p].end(), l);
		}
		return res;
	}

	inline int count(int ax, int ay, int bx, int by) {
		ax -= min_X - 1;
		ay -= min_Y - 1;
		bx -= min_X - 1;
		by -= min_Y - 1;
		return count(bx, ay, by) - count(ax - 1, ay, by);
	}
} c11, c12, c21, c22;

void init(int X, int Y, int x, int y, int M, char *S) {
	tomap['N'] = 0;
	tomap['E'] = 1;
	tomap['S'] = 2;
	tomap['W'] = 3;

	vector<pair<int, int>> path;
	path.emplace_back(x, y);

	min_X = max_X = x;
	min_Y = max_Y = y;

	for (int i = 0; i < M; i++) {
		x += dx[tomap[S[i]]];
		y += dy[tomap[S[i]]];
		path.emplace_back(x, y);
	}

	sort(path.begin(), path.end());
	path.erase(unique(path.begin(), path.end()), path.end());

	for (auto [x, y] : path) {
		min_X = min(min_X, x);
		max_X = max(max_X, x);
		min_Y = min(min_Y, y);
		max_Y = max(max_Y, y);

		c11.pre_add(x, y);
		
		c12.pre_add(x, y);
		c12.pre_add(x, y + 1);

		c21.pre_add(x, y);
		c21.pre_add(x + 1, y);

		c22.pre_add(x, y);
		c22.pre_add(x, y + 1);
		c22.pre_add(x + 1, y);
		c22.pre_add(x + 1, y + 1);
	}

	c11.work();
	c12.work();
	c21.work();
	c22.work();
}

int colour(int ax, int ay, int bx, int by) {
	int res = 0;

	res -= c11.count(ax, ay, bx, by);
	res += c12.count(ax, ay + 1, bx, by);
	res += c21.count(ax + 1, ay, bx, by);
	res -= c22.count(ax + 1, ay + 1, bx, by);

	return res + 1;
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:64:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   64 |   x += dx[tomap[S[i]]];
      |                 ~~~^
rainbow.cpp:65:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   65 |   y += dy[tomap[S[i]]];
      |                 ~~~^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19156 KB Output is correct
2 Correct 17 ms 19584 KB Output is correct
3 Incorrect 16 ms 19216 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 11 ms 19008 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 494 ms 51928 KB Output is correct
4 Correct 789 ms 76968 KB Output is correct
5 Correct 796 ms 76828 KB Output is correct
6 Correct 623 ms 70676 KB Output is correct
7 Correct 602 ms 65200 KB Output is correct
8 Correct 75 ms 20556 KB Output is correct
9 Correct 709 ms 76876 KB Output is correct
10 Correct 744 ms 76772 KB Output is correct
11 Correct 607 ms 70372 KB Output is correct
12 Correct 766 ms 75484 KB Output is correct
13 Correct 655 ms 76940 KB Output is correct
14 Correct 661 ms 76676 KB Output is correct
15 Correct 579 ms 70496 KB Output is correct
16 Correct 607 ms 68380 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 783 ms 77348 KB Output is correct
3 Correct 174 ms 58928 KB Output is correct
4 Correct 183 ms 57244 KB Output is correct
5 Correct 264 ms 53744 KB Output is correct
6 Correct 85 ms 28944 KB Output is correct
7 Incorrect 170 ms 38020 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19156 KB Output is correct
2 Correct 17 ms 19584 KB Output is correct
3 Incorrect 16 ms 19216 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19156 KB Output is correct
2 Correct 17 ms 19584 KB Output is correct
3 Incorrect 16 ms 19216 KB Output isn't correct
4 Halted 0 ms 0 KB -