제출 #676544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676544		ymm	무지개나라 (APIO17_rainbow)	C++17	100 / 100	799 ms	148932 KiB

rainbow

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
#include "rainbow.h"

struct seg {
	vector<int> *t;
	
	void init(int sz) { t = new vector<int>[4*sz]; }
	
	void add(int p, int x, int i, int b, int e) {
		if (e-b == 1) {
			t[i].push_back(x);
			return;
		}
		if (p < (b+e)/2)
			add(p, x, 2*i+1, b, (b+e)/2);
		else
			add(p, x, 2*i+2, (b+e)/2, e);
	}
	void build(int i, int b, int e) {
		if (e-b == 1) {
			sort(t[i].begin(), t[i].end());
			auto it = unique(t[i].begin(), t[i].end());
			t[i].resize(it - t[i].begin());
			return;
		}
		build(2*i+1, b, (b+e)/2);
		build(2*i+2, (b+e)/2, e);
		merge(t[2*i+1].begin(), t[2*i+1].end(),
		      t[2*i+2].begin(), t[2*i+2].end(),
		      back_inserter(t[i]));
	}
	int get(int l1, int r1, int l2, int r2, int i, int b, int e) {
		if (l1 <= b && e <= r1) {
			return   lower_bound(t[i].begin(), t[i].end(), r2)
			       - lower_bound(t[i].begin(), t[i].end(), l2);
		}
		if (r1 <= b || e <= l1)
			return 0;
		return   get(l1, r1, l2, r2, 2*i+1, b, (b+e)/2)
		       + get(l1, r1, l2, r2, 2*i+2, (b+e)/2, e);
	}
} seg_edge_h, seg_edge_v, seg_node, seg_river;
int n, m;
int rmn = INT_MAX, rmx = 0;
int cmn = INT_MAX, cmx = 0;

void add_river(int i, int j)
{
	seg_edge_h.add(i, j, 0, 0, n+1);
	seg_edge_h.add(i+1, j, 0, 0, n+1);
	seg_edge_v.add(i, j, 0, 0, n+1);
	seg_edge_v.add(i, j+1, 0, 0, n+1);
	seg_node.add(i, j, 0, 0, n+1);
	seg_node.add(i, j+1, 0, 0, n+1);
	seg_node.add(i+1, j, 0, 0, n+1);
	seg_node.add(i+1, j+1, 0, 0, n+1);
	seg_river.add(i, j, 0, 0, n);
	rmn = min(rmn, i);
	rmx = max(rmx, i);
	cmn = min(cmn, j);
	cmx = max(cmx, j);
}

void init(int R, int C, int sr, int sc, int M, char *S)
{
	n = R; m = C;
	seg_edge_h.init(n+1);
	seg_edge_v.init(n+1);
	seg_node.init(n+1);
	seg_river.init(n);
	int x = sr - 1, y = sc - 1;
	add_river(x, y);
	Loop (i,0,M) {
		char c = S[i];
		x -= c == 'N';
		x += c == 'S';
		y -= c == 'W';
		y += c == 'E';
		add_river(x, y);
	}
	seg_edge_h.build(0, 0, n+1);
	seg_edge_v.build(0, 0, n+1);
	seg_node.build(0, 0, n+1);
	seg_river.build(0, 0, n);
}

int colour(int ar, int ac, int br, int bc)
{
	--ar; --ac;
	int edges = 0, nodes = 0, rivers = 0, comps = 0;
	edges += seg_edge_h.get(ar+1, br, ac, bc, 0, 0, n+1);
	edges += seg_edge_v.get(ar, br, ac+1, bc, 0, 0, n+1);
	edges += 2*(br - ar) + 2*(bc - ac);
	nodes += seg_node.get(ar+1, br, ac+1, bc, 0, 0, n+1);
	nodes += 2*(br - ar) + 2*(bc - ac);
	rivers += seg_river.get(ar, br, ac, bc, 0, 0, n);
	comps = 1 + (ar < rmn && rmx+1 < br && ac < cmn && cmx+1 < bc);
	int ans = edges - nodes + comps - rivers;
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26