제출 #184027

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
184027		oolimry	무지개나라 (APIO17_rainbow)	C++14	100 / 100	1184 ms	99176 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200002; int totalRivers;
struct segment{
	vector<int> tree[2*N+5];
	inline void update(int i, int v){ tree[i+N].push_back(v); }
	inline void getReady(){
		for(int i = N;i < 2*N;i++){
			sort(tree[i].begin(),tree[i].end());
			tree[i].erase(unique(tree[i].begin(),tree[i].end()),tree[i].end());
		}
		for(int i = N-1;i > 0;i--){ ///basically merge sort
			tree[i] = vector<int>(tree[i<<1].size()+tree[i<<1|1].size());
			merge(tree[i<<1].begin(),tree[i<<1].end(), tree[i<<1|1].begin(),tree[i<<1|1].end(),tree[i].begin());
		}
	}
	inline int query(int l, int r, int x, int y){ 
		int ans = 0;
		for(l += N, r += (N+1);l < r;l >>= 1, r >>= 1){
			if(l&1) ans += upper_bound(tree[l].begin(),tree[l].end(),y) - lower_bound(tree[l].begin(),tree[l].end(),x), l++;
			if(r&1) r--, ans += upper_bound(tree[r].begin(),tree[r].end(),y) - lower_bound(tree[r].begin(),tree[r].end(),x);
		}
		return ans;
	}
} vertices, horizontal, vertical, faces;
void addRiver(int r, int c){
	vertices.update(r,c);
	horizontal.update(r,c-1); horizontal.update(r,c);
	vertical.update(c,r-1); vertical.update(c,r);
	faces.update(r-1,c-1); faces.update(r,c-1); faces.update(r-1,c); faces.update(r,c);
}
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--; else if(S[i] == 'S') sr++; else if(S[i] == 'E') sc++; else sc--;
		addRiver(sr,sc);
	}
	vertices.getReady(); horizontal.getReady(); vertical.getReady(); faces.getReady();
	totalRivers = vertices.query(0,N-1,0,N-1);
}
int colour(int T, int L, int B, int R) {
	long long H = B - T + 1, W = R - L + 1;
	long long V = H * W - vertices.query(T,B,L,R);
	long long E = (H-1)*W + (W-1)*H - horizontal.query(T,B,L,R-1) - vertical.query(L,R,T,B-1);
	long long F = (H-1)*(W-1) - faces.query(T,B-1,L,R-1);
	if(vertices.query(T+1,B-1,L+1,R-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