oj.uz

Submission #466258

# Submission time Handle Problem Language Result Execution time Memory
466258 2021-08-18T12:18:45 Z nonsensenonsense1 Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1801 ms 92892 KB 
#include "rainbow.h"
#include <algorithm>
#include <set>
#include <utility>
#include <vector>

const int N = 200005;
const int T = N * 400;
int size = N << 1, val[T], left[T];
std::vector<int> edge_h[N], edge_v[N], pt_h[N], pt_v[N];

void update_y(int ind, int i, int d, int tl = 0, int tr = N) 
{
	if (tr - tl != 1) {
		if (!left[ind]) {
			left[ind] = size;
			size += 2;
		}
		int m = tl + tr >> 1;
		if (i < m) update_y(left[ind], i, d, tl, m);
		else update_y(left[ind] | 1, i, d, m, tr);
	}
	val[ind] += d;
}

void update_x(int x, int y, int d) 
{
	for (x += N; x > 0; x >>= 1) update_y(x, y, d);
}

int query_y(int ind, int l, int r, int tl = 0, int tr = N) 
{
	if (tl >= r || tr <= l) return 0;
	if (tl >= l && tr <= r) return val[ind];
	if (!left[ind]) return 0;
	int m = tl + tr >> 1;
	return query_y(left[ind], l, r, tl, m) + query_y(left[ind] | 1, l, r, m, tr);
}

int query_x(int x1, int x2, int y1, int y2) 
{
	int ans = 0;
	for (x1 += N, x2 += N; x1 < x2; x1 >>= 1, x2 >>= 1) {
		if (x1 & 1) ans += query_y(x1++, y1, y2);
		if (x2 & 1) ans += query_y(--x2, y1, y2);
	}
	return ans;
}

void add(int x, int y, bool type) 
{
	if (type) edge_h[x].push_back(y);
	else edge_v[y].push_back(x);
	update_x(x, y, 1);
}

void add_point(int x, int y) 
{
	pt_h[x].push_back(y);
	pt_v[y].push_back(x);
	update_x(x, y, -1);
}

int start_x, start_y;

void init(int r, int c, int sr, int sc, int m, char *s) 
{
	--sr;
	--sc;
	start_x = sr;
	start_y = sc;
	std::set<std::pair<int, int> > u;
	for (int i = 0; i <= m; ++i) {
		if (!u.count(std::make_pair(sr, sc))) {
			u.insert(std::make_pair(sr, sc));
			update_x(sr, sc, -1);
			bool u_left = u.count(std::make_pair(sr, sc - 1)), u_up = u.count(std::make_pair(sr - 1, sc)), u_right = u.count(std::make_pair(sr, sc + 1)), u_down = u.count(std::make_pair(sr + 1, sc));
			if (!u_left) {
				add(sr, sc, 0);
				if (!u_up) add_point(sr, sc);
			}
			if (!u_up) {
				add(sr, sc, 1);
				if (!u_right) add_point(sr, sc + 1);
			}
			if (!u_right) {
				add(sr, sc + 1, 0);
				if (!u_down) add_point(sr + 1, sc + 1);
			}
			if (!u_down) {
				add(sr + 1, sc, 1);
				if (!u_left) add_point(sr + 1, sc);
			}
		}
		if (i < m) {
			if (s[i] == 'N') --sr;
			else if (s[i] == 'S') ++sr;
			else if (s[i] == 'W') --sc;
			else ++sc;
		}
	}
	for (int i = 0; i < N; ++i) {
		std::sort(edge_h[i].begin(), edge_h[i].end());
		std::sort(edge_v[i].begin(), edge_v[i].end());
		std::sort(pt_h[i].begin(), pt_h[i].end());
		std::sort(pt_v[i].begin(), pt_v[i].end());
	}
}

inline int count(std::vector<int> &v, int l, int r) 
{
	return std::lower_bound(v.begin(), v.end(), r) - std::lower_bound(v.begin(), v.end(), l);
}

int colour(int ar, int ac, int br, int bc) 
{
	--ar;
	--ac;
	return query_x(ar, br, ac, bc) - count(edge_h[ar], ac, bc) - count(edge_v[ac], ar, br) + count(pt_h[ar], ac, bc) + count(pt_v[ac], ar + 1, br) + 1 + (pt_h[ar].empty() && pt_h[br].empty() && pt_v[ac].empty() && pt_v[bc].empty() && start_x >= ar && start_x < br && start_y >= ac && start_y < bc);
}

Compilation message

rainbow.cpp: In function 'void update_y(int, int, int, int, int)':
rainbow.cpp:19:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |   int m = tl + tr >> 1;
      |           ~~~^~~~
rainbow.cpp: In function 'int query_y(int, int, int, int, int)':
rainbow.cpp:36:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |  int m = tl + tr >> 1;
      |          ~~~^~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 19220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19148 KB Output is correct
2 Correct 13 ms 19148 KB Output is correct
3 Correct 1095 ms 45728 KB Output is correct
4 Correct 1794 ms 62492 KB Output is correct
5 Correct 1766 ms 60200 KB Output is correct
6 Correct 1352 ms 44500 KB Output is correct
7 Correct 1375 ms 44152 KB Output is correct
8 Correct 104 ms 19908 KB Output is correct
9 Correct 1801 ms 62512 KB Output is correct
10 Correct 1755 ms 60192 KB Output is correct
11 Correct 1455 ms 44460 KB Output is correct
12 Correct 1561 ms 59840 KB Output is correct
13 Correct 1650 ms 62588 KB Output is correct
14 Correct 1660 ms 60140 KB Output is correct
15 Correct 1277 ms 44580 KB Output is correct
16 Correct 1277 ms 50468 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19072 KB Output is correct
2 Correct 1691 ms 63016 KB Output is correct
3 Correct 1549 ms 92892 KB Output is correct
4 Correct 1578 ms 75828 KB Output is correct
5 Correct 1255 ms 65160 KB Output is correct
6 Correct 326 ms 22700 KB Output is correct
7 Incorrect 638 ms 25732 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 19220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 19220 KB Output isn't correct
2 Halted 0 ms 0 KB -