oj.uz

Submission #466255

# Submission time Handle Problem Language Result Execution time Memory
466255 2021-08-18T12:16:07 Z nonsensenonsense1 Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1899 ms 92888 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 + (pt_h[ar].empty() && pt_h[br].empty() && pt_v[ac].empty() && pt_v[bc].empty());
}

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 17 ms 19208 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 19176 KB Output is correct
2 Correct 13 ms 19076 KB Output is correct
3 Correct 1104 ms 45968 KB Output is correct
4 Correct 1899 ms 62800 KB Output is correct
5 Correct 1828 ms 60408 KB Output is correct
6 Correct 1409 ms 44712 KB Output is correct
7 Correct 1469 ms 44368 KB Output is correct
8 Correct 90 ms 20168 KB Output is correct
9 Correct 1815 ms 62792 KB Output is correct
10 Correct 1871 ms 60408 KB Output is correct
11 Correct 1372 ms 44720 KB Output is correct
12 Correct 1569 ms 59968 KB Output is correct
13 Correct 1691 ms 62852 KB Output is correct
14 Correct 1674 ms 60524 KB Output is correct
15 Correct 1288 ms 44844 KB Output is correct
16 Correct 1253 ms 50964 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19148 KB Output is correct
2 Correct 1661 ms 63192 KB Output is correct
3 Correct 1550 ms 92888 KB Output is correct
4 Correct 1538 ms 76036 KB Output is correct
5 Correct 1273 ms 65140 KB Output is correct
6 Incorrect 333 ms 22640 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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