Submission #1266360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266360		PlayVoltz	Land of the Rainbow Gold (APIO17_rainbow)	C++20	100 / 100	1351 ms	247188 KiB

rainbow

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

#define int long long
#define pb push_back

struct node{
	int s, e, m;
	vector<int> val;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if (s!=e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void up(int ind, int nv){
		if (s==e)val.pb(nv);
		else{
			if (ind<=m)l->up(ind, nv);
			else r->up(ind, nv);
		}
	}
	void init(){
		if (s!=e)l->init(), r->init(), merge(l->val.begin(), l->val.end(), r->val.begin(), r->val.end(), back_inserter(val));
		else{
			sort(val.begin(), val.end());
			val.erase(unique(val.begin(), val.end()), val.end());
		}
	}
	int query(int a, int x, int b, int y){
		if (a>b||x>y)return 0;
		if (s==a && e==b){
			return upper_bound(val.begin(), val.end(), y)-lower_bound(val.begin(), val.end(), x);
		}
		if (b<=m)return l->query(a, x, b, y);
		else if (a>m)return r->query(a, x, b, y);
		return l->query(a, x, m, y)+r->query(m+1, x, b, y);
	}
}*black, *hori, *vert, *dot;

void add(int x, int y){
	black->up(x, y);
	hori->up(x, y);
	hori->up(x+1, y);
	vert->up(x, y);
	vert->up(x, y+1);
	dot->up(x, y);
	dot->up(x+1, y);
	dot->up(x, y+1);
	dot->up(x+1, y+1);
}

int ccc=0;

void init(signed r, signed c, signed x, signed y, signed m, char *s){
	black = new node(1, r+1);
	hori = new node(1, r+1);
	vert = new node(1, r+1);
	dot = new node(1, r+1);
	add(x, y);
	for (int i=0; i<m; ++i){
		if (s[i]=='N')--x;
		else if (s[i]=='S')++x;
		else if (s[i]=='W')--y;
		else ++y;
		add(x, y);
	}
	black->init(), hori->init(), vert->init(), dot->init();
	ccc=black->query(1, 1, r+1, c+1);
}

signed colour(signed a, signed b, signed x, signed y){
	int e=2*(y-b+1)+2*(x-a+1)+hori->query(a+1, b, x, y)+vert->query(a, b+1, x, y);
	int v=dot->query(a+1, b+1, x, y)+2*(x-a+2)+2*(y-b);
	return (black->query(a+1, b+1, x-1, y-1)==ccc?2:1)-v+e-black->query(a, b, x, y);
}

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