Submission #543404

#	Time	Username	Problem	Language	Result	Execution time	Memory
543404		amunduzbaev	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	2065 ms	235880 KiB

rainbow

#include "rainbow.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

#define int long long 
#define i32 int32_t
#define ar array
const int N = 2e5 + 5;

struct MSST{
	vector<int> tree[N << 2];
	void add(int i, int y, int lx = 0, int rx = N, int x = 1){
		tree[x].push_back(y);
		if(lx == rx) return;
		int m = (lx + rx) >> 1;
		if(i <= m) add(i, y, lx, m, x<<1);
		else add(i, y, m+1, rx, x<<1|1);
	}
	
	void build(int lx = 0, int rx = N, int x = 1){
		sort(tree[x].begin(), tree[x].end());
		if(lx == rx) return;
		int m = (lx + rx) >> 1;
		build(lx, m, x<<1), build(m+1, rx, x<<1|1);
	}
	
	int get(int l, int r, int l_, int r_, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r){
			auto R = upper_bound(tree[x].begin(), tree[x].end(), r_);
			auto L = lower_bound(tree[x].begin(), tree[x].end(), l_);
			return R - L;
		} int m = (lx + rx) >> 1;
		return get(l, r, l_, r_, lx, m, x<<1) + get(l, r, l_, r_, m+1, rx, x<<1|1);
	}
}ed[2], ver, sq; //, ver, sq;
set<ar<int, 2>> ss, tot, is[2];
int Lx, Rx, Ly, Ry;

void init(i32 n, i32 m, i32 x, i32 y, i32 k, char *s) {
	ss.insert({x, y});
	Lx = Rx = x, Ly = Ry = y;
	for(int i=0;i<k;i++){
		if(s[i] == 'N') x--;
		if(s[i] == 'S') x++;
		if(s[i] == 'W') y--;
		if(s[i] == 'E') y++;
		ss.insert({x, y});
		Lx = min(Lx, 1ll * x);
		Rx = max(Rx, 1ll * x);
		Ly = min(Ly, 1ll * y);
		Ry = max(Ry, 1ll * y);
	}
	
	for(auto x : ss){
		//~ cout<<x[0]<<" "<<x[1]<<"\n";
		is[0].insert(x);
		is[0].insert({x[0] + 1, x[1]});
		is[1].insert(x);
		is[1].insert({x[0], x[1] + 1});
		tot.insert(x);
		tot.insert({x[0] + 1, x[1]});
		tot.insert({x[0], x[1] + 1});
		tot.insert({x[0] + 1, x[1] + 1});
		sq.add(x[0], x[1]);
	}
	
	for(auto x : tot){
		if(is[0].count(x)) ed[0].add(x[0], x[1]);
		if(is[1].count(x)) ed[1].add(x[0], x[1]);
		ver.add(x[0], x[1]);
	}
	
	ed[0].build();
	ed[1].build();
	ver.build();
	sq.build();
}

/*

6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3

13 13 13 1
6 8
WWWEENWEEWEWE
3 4 10 13

13 13 26 1
5 9
SEWSWEENSNSNSEENSNSNNNWWSN
1 5 8 13

*/

i32 colour(i32 lx, i32 ly, i32 rx, i32 ry) {
	if(lx > rx) swap(lx, rx);
	if(ly > ry) swap(ly, ry);
	int ee = ed[0].get(lx, rx + 1, ly, ry);
	ee += ed[1].get(lx, rx, ly, ry + 1);
	int V = ver.get(lx, rx + 1, ly, ry + 1);
	int tmp = 0, tt = 0;
	tmp += ver.get(lx, lx, ly, ry + 1);
	tt += ed[0].get(lx, lx, ly, ry);
	
	tmp += ver.get(rx + 1, rx + 1, ly, ry + 1);
	tt += ed[0].get(rx + 1, rx + 1, ly, ry);
	
	if(lx < rx) tmp += ver.get(lx + 1, rx, ly, ly);
	tt += ed[1].get(lx, rx, ly, ly);
	
	if(lx < rx) tmp += ver.get(lx + 1, rx, ry + 1, ry + 1);
	tt += ed[1].get(lx, rx, ry + 1, ry + 1);
	
	int v = (rx - lx + ry - ly + 2) * 2;
	V += (v - tmp);
	ee += (v - tt);
	//~ cout<<tmp<<" "<<tt<<"\n";
	int F = sq.get(lx, rx, ly, ry);
	//~ assert(1 - V + ee - F >= 0);
	int res = (1 - V + ee - F);
	if(lx < Lx && Rx < rx && ly < Ly && Ry < ry){
		res++;
	}
	return res;
}

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