Submission #118278

#	Time	Username	Problem	Language	Result	Execution time	Memory
118278		tmwilliamlin168	Land of the Rainbow Gold (APIO17_rainbow)	C++14	12 / 100	1229 ms	78412 KiB

rainbow

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

const int mxN=2e5, mxSTS=1e5*19+1;

struct pst {
	vector<int> ta[mxN];
	int rt[mxN+1], sts=1, st[mxSTS], lc[mxSTS], rc[mxSTS];
	void a(array<int, 2> a) {
		ta[a[0]].push_back(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-1) {
		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-1)-qry(l2, r2, rt[l1], 0, mxN-1);
	}
	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);
	}
} stv, ster, stec, sts;

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) {
		stv.a(a);
		if(cs.find({a[0], a[1]+1})!=cs.end())
			ster.a(a);
		if(cs.find({a[0]+1, a[1]})!=cs.end())
			stec.a(a);
		if(cs.find({a[0], a[1]+1})!=cs.end()&&cs.find({a[0]+1, a[1]})!=cs.end()&&cs.find({a[0]+1, a[1]+1})!=cs.end())
			sts.a(a);
	}
	stv.bld();
	ster.bld();
	stec.bld();
	sts.bld();
}

int colour(int ar, int ac, int br, int bc) {
	--ar, --ac, --br, --bc;
	int e=2*(br-ar+bc-ac+4)+ster.qry(ar, br, ac, bc-1)+stec.qry(ar, br-1, ac, bc)+stv.qry(ar, ar, ac, bc)+stv.qry(br, br, ac, bc)+stv.qry(ar, br, ac, ac)+stv.qry(ar, br, bc, bc);
	int v=2*(br-ar+bc-ac+4)+stv.qry(ar, br, ac, bc);
	int c=!stv.qry(ar, br, ac, bc)||stv.qry(ar, br, ac, bc)-stv.qry(ar+1, br-1, ac+1, bc-1)?1:2;
	int s=stv.qry(ar, ar, ac, ac)+stv.qry(ar, ar, bc, bc)+stv.qry(br, br, ac, ac)+stv.qry(br, br, bc, bc)+ster.qry(ar, ar, ac, bc-1)+ster.qry(br, br, ac, bc-1)+stec.qry(ar, br-1, ac, ac)+stec.qry(ar, br-1, bc, bc)+sts.qry(ar, br-1, ac, bc-1);
    return e-v+c-s;
}

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