제출 #466255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
466255		nonsensenonsense1	무지개나라 (APIO17_rainbow)	C++17	12 / 100	1899 ms	92888 KiB

rainbow

#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());
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26