제출 #561982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
561982		maximath_1	무지개나라 (APIO17_rainbow)	C++11	100 / 100	891 ms	98768 KiB

rainbow

#include "rainbow.h"
#include <vector>
#include <algorithm>
using namespace std;

#define ll long long
const int MX = 2e5 + 5;

struct segmentTree{
	vector<int> st[MX * 2 + 5];
	void upd(int ps, int val){
		st[ps + MX].push_back(val);
	}
	void proc(){
		for(int i = MX; i < 2 * MX; i ++){
			sort(st[i].begin(), st[i].end());
			st[i].erase(unique(st[i].begin(), st[i].end()), st[i].end());
		}
		for(int i = MX - 1; i > 0; i --){
			st[i] = vector<int>(st[i * 2].size() + st[i * 2 + 1].size());
			merge(st[i * 2].begin(), st[i * 2].end(), st[i * 2 + 1].begin(), st[i * 2 + 1].end(), st[i].begin());
		}
	}
	int que(int lf, int rg, int x, int y){
		int ans = 0;
		for(lf += MX, rg += MX + 1; lf < rg; lf /= 2, rg /= 2){
			if(lf % 2)
				ans += upper_bound(st[lf].begin(), st[lf].end(), y) - lower_bound(st[lf].begin(), st[lf].end(), x), lf ++;
			if(rg % 2)
				rg --, ans += upper_bound(st[rg].begin(), st[rg].end(), y) - lower_bound(st[rg].begin(), st[rg].end(), x);
		}
		return ans;
	}
} vertex, hori, verti, face;

int totalRivers = 0;

void addRiver(int x, int y){
	vertex.upd(x, y);
	hori.upd(x, y - 1); hori.upd(x, y);
	verti.upd(y, x - 1); verti.upd(y, x);
	face.upd(x - 1, y - 1); face.upd(x, y - 1); face.upd(x - 1, y); face.upd(x, y);
}

void init(int R, int C, int sr, int sc, int M, char *s) {
	addRiver(sr, sc);
	for(int i = 0; i < M; i ++){
		if(s[i] == 'N') sr --;
		if(s[i] == 'S') sr ++;
		if(s[i] == 'E') sc ++;
		if(s[i] == 'W') sc --;
		addRiver(sr, sc);
	}

	vertex.proc(); hori.proc(); verti.proc(); face.proc();
	totalRivers = vertex.que(0, MX - 1, 0, MX - 1);
}

int colour(int ar, int ac, int br, int bc) {
	ll H = br - ar + 1, W = bc - ac + 1;
	ll V = H * W - vertex.que(ar, br, ac, bc);
	ll E = (H - 1) * W + (W - 1) * H - hori.que(ar, br, ac, bc - 1) - verti.que(ac, bc, ar, br - 1);
	ll F = (H - 1) * (W - 1) - face.que(ar, br - 1, ac, bc - 1);
	if(vertex.que(ar + 1, br - 1, ac + 1, bc - 1) == totalRivers) F ++;
    return V - E + F;
}

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