제출 #676921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676921		kingfran1907	무지개나라 (APIO17_rainbow)	C++14	12 / 100	876 ms	411332 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;
const int logo = 19;
const int off = 1 << logo;
const int treesiz = off << 1;

struct node {
	node *l, *r;
	int val;
	node() {
		l = r = nullptr;
		val = 0;
	}
};
typedef node* pnode;

inline pnode L(pnode tren) {
	if (tren == nullptr) return nullptr;
	return tren->l;
}

inline pnode R(pnode tren) {
	if (tren == nullptr) return nullptr;
	return tren->r;
}

inline int value(pnode tren) {
	if (tren == nullptr) return 0;
	return tren->val;
}

void update(pnode tren, pnode prev, int x, int l, int r, int val) {
	if (l > x || r < x) return;
	if (x == l && x == r) {
		tren->val = value(prev) + val;
		return;
	}

	int mid = (l + r) / 2;
	if (x <= mid) {
		tren->l = new node();
		tren->r = R(prev);
		update(tren->l, L(prev), x, l, mid, val);
	} else {
		tren->r = new node();
		tren->l = L(prev);
		update(tren->r, R(prev), x, mid + 1, r, val);
	}
	tren->val = value(tren->l) + value(tren->r);
}

int query(pnode tren, int a, int b, int l, int r) {
	if (tren == nullptr) return 0;
	if (l > b || r < a) return 0;
	if (l >= a && r <= b) return tren->val;
	
	int mid = (l + r) / 2;
	return query(tren->l, a, b, l, mid) + query(tren->r, a, b, mid + 1, r);
}

struct tournament {
	pnode root[maxn];
	int kol;
	tournament() {
		kol = 0;
		for (int i = 0; i < maxn; i++) 
			root[i] = nullptr;
	}
	
	void add(vector< int > &v) {
		pnode ptr = root[kol];
		kol++;
		for (int tren : v) {
			pnode nw = new node();
			update(nw, ptr, tren, 0, off - 1, 1);
			ptr = nw;
		}
		root[kol] = ptr;
	}
	
	int query(int x1, int y1, int x2, int y2) {
		if (x1 > x2 || y1 > y2) return 0;
		return ::query(root[x2], y1, y2, 0, off - 1) - ::query(root[x1 - 1], y1, y2, 0, off - 1);
	}
} vert, faces, edgesx, edgesy;

void insert(set< pair<int, int> > &s, tournament &tour) {
	auto iter = s.begin();
	for (int i = 1; i < maxn; i++) {
		vector< int > v;
		while (iter != s.end() && iter->X == i) {
			v.push_back(iter->Y);
			iter++;
		}
		tour.add(v);
	}
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	set< pair<int, int> > s;
	s.insert({sr, sc});
	for (int i = 0; i < M; i++) {
		if (S[i] == 'N') sr--;
		else if (S[i] == 'S') sr++;
		else if (S[i] == 'W') sc--;
		else sc++;
		s.insert({sr, sc});
	}
	
	auto iter = s.begin();
	set< pair<int, int> > ac;
	set< pair<int, int> > xv, yv;
	for (int i = 1; i < maxn; i++) {
		vector< int > v;
		while (iter != s.end() && iter->X == i) {
			for (int x = 0; x < 2; x++)
				for (int y = 0; y < 2; y++)
					ac.insert({iter->X + x, iter->Y + y});
			xv.insert(*iter); xv.insert({iter->X + 1, iter->Y});
			yv.insert(*iter); yv.insert({iter->X, iter->Y + 1});
			
			v.push_back(iter->Y);
			iter++;
		}
		vert.add(v);
	}
	insert(ac, faces);
	insert(xv, edgesx);
	insert(yv, edgesy);
}

int colour(int ar, int ac, int br, int bc) {
	llint v = (llint)(br - ar + 1) * (bc - ac + 1) - vert.query(ar, ac, br, bc);
	llint f = (llint)(br - ar) * (bc - ac) - faces.query(ar + 1, ac + 1, br, bc);
	llint e = (llint)(br - ar + 1) * (bc - ac) + (llint)(br - ar) * (bc - ac + 1);
	e -= edgesx.query(ar + 1, ac, br, bc);
	e -= edgesy.query(ar, ac + 1, br, bc);
	
	//printf("debug: %lld %lld %lld\n", v, e, f);
	assert(v + f - e >= 0);
   	return v + f - e;
}

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