oj.uz

Submission #466245

# Submission time Handle Problem Language Result Execution time Memory
466245 2021-08-18T11:47:18 Z nonsensenonsense1 Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1784 ms 92928 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);
}

void init(int r, int c, int sr, int sc, int m, char *s) 
{
	--sr;
	--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;
}

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 19148 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 11 ms 19148 KB Output is correct
2 Correct 12 ms 19148 KB Output is correct
3 Correct 1110 ms 48584 KB Output is correct
4 Correct 1784 ms 65428 KB Output is correct
5 Correct 1740 ms 63036 KB Output is correct
6 Correct 1385 ms 47420 KB Output is correct
7 Correct 1398 ms 46988 KB Output is correct
8 Correct 91 ms 22852 KB Output is correct
9 Correct 1770 ms 65364 KB Output is correct
10 Correct 1760 ms 63012 KB Output is correct
11 Correct 1413 ms 47392 KB Output is correct
12 Correct 1563 ms 62564 KB Output is correct
13 Correct 1653 ms 65352 KB Output is correct
14 Correct 1638 ms 63108 KB Output is correct
15 Correct 1280 ms 47320 KB Output is correct
16 Correct 1295 ms 53336 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19148 KB Output is correct
2 Correct 1687 ms 63380 KB Output is correct
3 Correct 1605 ms 92928 KB Output is correct
4 Correct 1552 ms 75992 KB Output is correct
5 Correct 1282 ms 65308 KB Output is correct
6 Correct 311 ms 22656 KB Output is correct
7 Incorrect 651 ms 25632 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 19148 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 19148 KB Output isn't correct
2 Halted 0 ms 0 KB -