Submission #118412

#	Time	Username	Problem	Language	Result	Execution time	Memory
118412		tmwilliamlin168	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1954 ms	210500 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=2e5, mxSTS=(6e5+9)*19+1;
int sts=1, st[mxSTS], lc[mxSTS], rc[mxSTS];

struct dat {
	set<int> ta[mxN+1];
	int rt[mxN+2];
	void a(array<int, 2> a) {
		ta[a[0]].insert(a[1]);
	}
	void bld() {
		for(int i=0; i<=mxN; ++i) {
			rt[i+1]=rt[i];
			for(int j : ta[i])
				upd(j, rt[i+1]);
		}
	}
	void upd(int l1, int &i, int l2=0, int r2=mxN) {
		st[sts]=st[i]+1;
		lc[sts]=lc[i];
		rc[sts]=rc[i];
		i=sts++;
		if(l2==r2)
			return;
		int m2=(l2+r2)/2;
		if(l1<=m2)
			upd(l1, lc[i], l2, m2);
		else
			upd(l1, rc[i], m2+1, r2);
	}
	int qry(int l1, int r1, int l2, int r2) {
		return l2>r2?0:qry(l2, r2, rt[r1+1], 0, mxN)-qry(l2, r2, rt[l1], 0, mxN);
	}
	int qry(int l1, int r1, int i, int l2, int r2) {
		if(l1<=l2&&r2<=r1)
			return st[i];
		int m2=(l2+r2)/2;
		return (l1<=m2?qry(l1, r1, lc[i], l2, m2):0)+(m2<r1?qry(l1, r1, rc[i], m2+1, r2):0);
	}
} sv, ser, sec, ss;

void init(int r, int c, int sr, int sc, int m, char *s) {
	set<array<int, 2>> cs{{--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;
		cs.insert({sr, sc});
	}
	for(auto a : cs) {
		sv.a(a);
		sv.a({a[0], a[1]+1});
		sv.a({a[0]+1, a[1]});
		sv.a({a[0]+1, a[1]+1});
		ser.a(a);
		ser.a({a[0]+1, a[1]});
		sec.a(a);
		sec.a({a[0], a[1]+1});
		ss.a(a);
	}
	sv.bld();
	ser.bld();
	sec.bld();
	ss.bld();
}

int colour(int ar, int ac, int br, int bc) {
	--ar, --ac, --br, --bc;
	int e=2*(br-ar+bc-ac+2)+ser.qry(ar+1, br, ac, bc)+sec.qry(ar, br, ac+1, bc);
	int v=2*(br-ar+bc-ac+2)+sv.qry(ar+1, br, ac+1, bc);
	int s=ss.qry(ar, br, ac, bc);
	int c=!sv.qry(ar+1, br, ac+1, bc)||ser.qry(ar+1, br, ac, bc)-ser.qry(ar+1, br, ac+1, bc-1)||sec.qry(ar, br, ac+1, bc)-sec.qry(ar+1, br-1, ac+1, bc)?1:2;
    return e-v+c-s;
}

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