Submission #1136139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136139		boyliguanhan	Land of the Rainbow Gold (APIO17_rainbow)	C++20	100 / 100	668 ms	202788 KiB

rainbow

#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
struct segtreeee{
	set<int> st[200100];
	int rt[200100],CC;
	struct nod{
		int v,lc,rc;
	} seg[1<<24];
	void ins(int a,int b){
		st[a].insert(b);
	}
	void upd(int &i,int l,int r,int p){
		seg[++CC]=seg[i];
		i=CC;
		seg[i].v++;
		if(l==r) return;
		if(p<=l+r>>1)upd(seg[i].lc,l,l+r>>1,p);
		else upd(seg[i].rc,l+r+2>>1,r,p);
	}
	void dostuf(){
		for(int i=1;i<=2e5;i++){
			rt[i]=rt[i-1];
			for(auto j:st[i])
				upd(rt[i],1,2e5,j);
		}
	}
	int query(int i,int l,int r,int ll,int rr){
		if(!i)return 0;
		if(ll<=l&&r<=rr)
			return seg[i].v;
		if(ll>r||l>rr)
			return 0;
		return query(seg[i].lc,l,l+r>>1,ll,rr)+
				query(seg[i].rc,l+r+2>>1,r,ll,rr);
	}
	int calc(int l1,int r1,int l2,int r2){
		return query(rt[r1],1,2e5,l2,r2)-query(rt[l1-1],1,2e5,l2,r2);
	}
} V,EH,EV,riv;
int bot,lef,rit,top;
void add_river(int x, int y) {
	V.ins(x, y);
	V.ins(x + 1, y);
	V.ins(x, y + 1);
	V.ins(x + 1, y + 1);
	EH.ins(x, y);
	EH.ins(x + 1, y);
	EV.ins(x, y);
	EV.ins(x, y + 1);
	riv.ins(x, y);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
	add_river(sr, sc);
	bot = top = sr;
	lef = rit = sc;
	for(int i=0;i<M;i++){
		if (S[i] == 'N') sr--;
		if (S[i] == 'E') sc++;
		if (S[i] == 'S') sr++;
		if (S[i] == 'W') sc--;
		add_river(sr, sc);
		bot = max(bot, sr);
		top = min(top, sr);
		lef = max(lef, sc);
		rit = min(rit, sc);
	}
	V.dostuf();
	EH.dostuf();
	EV.dostuf();
	riv.dostuf();
}

int colour(int ar, int ac, int br, int bc) {
	int E = EH.calc(ar + 1, br, ac, bc) +
			EV.calc(ar, br, ac + 1, bc);
	int v = V.calc(ar + 1, br, ac + 1, bc);
	int R = riv.calc(ar, br, ac, bc);
	int C = (ar >= top || br <= bot || ac >= rit || bc <= lef ? 1 : 2);
	return E - v + C - R;
}

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