Submission #107376

#	Time	Username	Problem	Language	Result	Execution time	Memory
107376		tjd229	Land of the Rainbow Gold (APIO17_rainbow)	C++11	100 / 100	1973 ms	146480 KiB

rainbow

#include "rainbow.h"
#include <stdio.h>
#include <memory.h>
#include <vector>
#include <algorithm>
#define pii pair<int,int>
using namespace std;
const int LEAF = 1 << 18;
const int MEM = 8e6;
//v,ve,he,sq
int st_v[MEM], st_ve[MEM], st_he[MEM], st_sq[MEM];
int l_v[MEM], l_ve[MEM], l_he[MEM], l_sq[MEM];
int r_v[MEM], r_ve[MEM],r_he[MEM], r_sq[MEM];
int rt_v[LEAF], rt_ve[LEAF], rt_he[LEAF], rt_sq[LEAF];
int v, ve, he, sq;
int max_x, max_y, min_x, min_y;
int _R, _C;
inline void unq_sort(vector<pii > &v) {
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end())-v.begin());

}
int make_tree(int pre,int s,int e,int pos,int *st, int *l, int *r, int &cnt) {
	if (pos<s || pos>e) return pre;
	int ix = ++cnt;
	if (s == e) st[ix] = st[pre] + 1;
	else {
		l[ix] = make_tree(l[pre], s, (s + e) >> 1, pos, st, l, r, cnt);
		r[ix] = make_tree(r[pre], 1+( (s + e) >> 1),e, pos, st, l, r, cnt);
		st[ix] = st[l[ix]] + st[r[ix]];
	}
	return ix;
}
void make_tree(vector<pii > &v,int *root,int *st,int *l,int *r,int &cnt) {
	auto it = v.begin();
	for (int y = 1; y <= _R; ++y) {
		if (it != v.end() && y == it->first) {
			int pre = root[y - 1];
			while (it != v.end() && y == it->first) {
				pre = root[y] = make_tree(pre, 0, LEAF - 1, it->second, st, l, r, cnt);
				++it;
			}
		}
		else root[y] = root[y - 1];
	}
}
int range_sum(int ix, int s,int e,int from,int to, int *st, int *l, int *r) {
	if (ix == 0) return 0;
	else if (e < from || to < s) return 0;
	else if (from <= s && e <= to) return st[ix];
	return range_sum(l[ix], s, (s + e) >> 1, from, to, st, l, r)
		+ range_sum(r[ix], 1 + ((s + e) >> 1), e, from, to, st, l, r);
}
int sum(int y1,int x1,int y2,int x2,int *root,int *st, int *l, int *r) {
	if (x2 < x1 || y2 < y1) return 0;

	return range_sum(root[y2], 0, LEAF - 1, x1, x2, st, l, r)
		- range_sum(root[y1 - 1], 0, LEAF - 1, x1, x2, st, l, r);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
	_R = R; _C = C;
	v = ve = he = sq = 0;
	max_x = max_y = 0; min_x = C+1; min_y = R+1;
	vector<pii > vv,vve,vhe,vsq;
	vsq.push_back({sr,sc});//y,x
	for (int i = 0; i < M; ++i) {
		switch (S[i]) {
		case 'N':
			--sr; break;
		case 'E':
			++sc; break;
		case 'S':
			++sr; break;
		case 'W':
			--sc; break;
		}
		vsq.push_back({ sr,sc });
	}
	unq_sort(vsq);
	for (auto p : vsq) {
		vv.push_back(p); vv.push_back({ p.first,p.second + 1 });
		vv.push_back({ p.first + 1,p.second}); vv.push_back({ p.first+1,p.second + 1 });
		vve.push_back(p); vve.push_back({ p.first,p.second + 1 });
		vhe.push_back(p); vhe.push_back({ p.first+1,p.second });
		min_x = min(min_x, p.second); max_x = max(max_x, p.second + 1);
		min_y = min(min_y, p.first); max_y = max(max_y, p.first + 1);
	}
	_R = max(_R, max_y); _C = max(_C, max_x);
	unq_sort(vv); unq_sort(vve); unq_sort(vhe);
	make_tree(vsq, rt_sq, st_sq, l_sq, r_sq, sq);

	make_tree(vv, rt_v, st_v, l_v, r_v, v);
	make_tree(vve, rt_ve, st_ve, l_ve, r_ve, ve);
	make_tree(vhe, rt_he, st_he, l_he, r_he, he);
}
int colour(int ar, int ac, int br, int bc) {
	//return 0;
	int v = br + br + 4 - ar - ar + bc + bc + 4 - ac - ac - 4;
	int e = v;
	v += sum(ar + 1, ac + 1, br, bc,rt_v,st_v,l_v,r_v);
	e += sum(ar, ac+1, br, bc, rt_ve, st_ve, l_ve, r_ve)
		+ sum(ar+1, ac, br, bc, rt_he, st_he, l_he, r_he);
	int sq = sum(ar,ac,br,bc,rt_sq,st_sq,l_sq,r_sq);
	//printf("%d,%d,%d\n",v,e,sq);
	//printf("%d,%d,%d,%d\n",min_x,max_x,min_y,max_y);
	int f = 2 + e - v - sq;
	if (ac < min_x && ar < min_y && max_x <= bc && max_y <= br) ++f;
    return f-1;
}

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