제출 #160723

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160723		songc	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	310 ms	196628 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, R, C;
set<pii> P;

struct Node{
	int val=0;
	int lc=0, rc=0;
};

struct PST{
	int rt[202020], cnt=1;
	Node T[4040404];

	void update(int pre, int now, int s, int e, int t){
		if (pre != now) T[now].val = T[pre].val;
		T[now].val++;
		if (s == e) return;
		int mid = (s+e)/2;
		if (t <= mid){
			if (!T[now].lc) {
				T[now].lc = cnt++;
				T[now].rc = T[pre].rc;
			}
			update(T[pre].lc, T[now].lc, s, mid, t);
		}
		else{
			if (!T[now].rc) {
				T[now].rc = cnt++;
				T[now].lc = T[pre].lc;
			}
			update(T[pre].rc, T[now].rc, mid+1, e, t);
		}
	}

	int query(int now, int s, int e, int ts, int te){
		if (e < ts || te < s || T[now].val == 0) return 0;
		if (ts <= s && e <= te) return T[now].val;
		int mid = (s+e)/2;
		return query(T[now].lc, s, mid, ts, te)+query(T[now].rc, mid+1, e, ts, te);
	}
} V, HE, VE, F;


void init(int _R, int _C, int sr, int sc, int _M, char *S) {
	R = _R, C = _C, N = _M;
	P.insert(pii(sr, sc));
	for (int i=0; i<N; i++){
		if (S[i] == 'N') sr--;
		if (S[i] == 'S') sr++;
		if (S[i] == 'W') sc--;
		if (S[i] == 'E') sc++;
		P.insert(pii(sr, sc));
	}
	int lr=0;
	for (pii it : P){
		for (int i=lr+1; i<it.first; i++){
			V.rt[it.first] = V.rt[lr]; 
			HE.rt[it.first] = HE.rt[lr]; 
			VE.rt[it.first] = VE.rt[lr]; 
			F.rt[it.first] = F.rt[lr]; 
		}

		if (!V.rt[it.first]) V.rt[it.first] = V.cnt++;
		V.update(V.rt[it.first-1], V.rt[it.first], 1, C, it.second);

		if (P.find(pii(it.first, it.second+1)) != P.end()){
			if (!HE.rt[it.first]) HE.rt[it.first] = HE.cnt++;
			HE.update(HE.rt[it.first-1], HE.rt[it.first], 1, C, it.second);
		}
		else if (!HE.rt[it.first]) HE.rt[it.first] = HE.rt[it.first-1];

		if (P.find(pii(it.first+1, it.second)) != P.end()){
			if (!VE.rt[it.first]) VE.rt[it.first] = VE.cnt++;
			VE.update(VE.rt[it.first-1], VE.rt[it.first], 1, C, it.second);
		}
		else if (!VE.rt[it.first]) VE.rt[it.first] = VE.rt[it.first-1];

		if (P.find(pii(it.first+1, it.second+1)) != P.end()
			&& P.find(pii(it.first, it.second+1)) != P.end()
			&& P.find(pii(it.first+1, it.second)) != P.end()){
			if (!F.rt[it.first]) F.rt[it.first] = F.cnt++;
			F.update(F.rt[it.first-1], F.rt[it.first], 1, C, it.second);
		}
		else if (!F.rt[it.first]) F.rt[it.first] = F.rt[it.first-1];

		lr = it.first;
	}
	for (int i=lr+1; i<=R; i++){
		V.rt[i] = V.rt[lr];
		HE.rt[i] = HE.rt[lr];
		VE.rt[i] = VE.rt[lr];
		F.rt[i] = F.rt[lr];
	}
}

int colour(int ar, int ac, int br, int bc) {
	int ret = 1;
	if (ar < br) ret += HE.query(HE.rt[br-1], 1, C, ac, bc-1) - HE.query(HE.rt[ar], 1, C, ac, bc-1);
	ret += VE.query(VE.rt[br-1], 1, C, ac+1, bc-1) - VE.query(VE.rt[ar-1], 1, C, ac+1, bc-1);
	
	ret += V.query(V.rt[ar], 1, C, ac, bc) - V.query(V.rt[ar-1], 1, C, ac, bc);
	ret += V.query(V.rt[br], 1, C, ac, bc) - V.query(V.rt[br-1], 1, C, ac, bc);
	ret += V.query(V.rt[br], 1, C, ac, ac) - V.query(V.rt[ar-1], 1, C, ac, ac);
	ret += V.query(V.rt[br], 1, C, bc, bc) - V.query(V.rt[ar-1], 1, C, bc, bc);
    
    ret -= V.query(V.rt[br], 1, C, ac, bc) - V.query(V.rt[ar-1], 1, C, ac, bc);
    ret -= F.query(F.rt[br-1], 1, C, ac, bc-1) - F.query(F.rt[ar-1], 1, C, ac, bc-1);
    if (P.find(pii(ar, ac)) != P.end()) ret--;
    if (P.find(pii(ar, bc)) != P.end()) ret--;
    if (P.find(pii(br, ac)) != P.end()) ret--;
    if (P.find(pii(br, bc)) != P.end()) ret--;
    return ret;
}

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