Submission #543324

#	Time	Username	Problem	Language	Result	Execution time	Memory
543324		amunduzbaev	Land of the Rainbow Gold (APIO17_rainbow)	C++17	12 / 100	1579 ms	233696 KiB

rainbow

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

#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){
		tree[x].push_back(-1);
		tree[x].push_back(N);
		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;
vector<int> row[N], col[N], erow[N], ecol[N];
set<ar<int, 2>> ss, tot, is[2];

void init(int n, int m, int x, int y, int k, char *s) {
	ss.insert({x, 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});
	}
	
	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]), erow[x[0]].push_back(x[1]);
		if(is[1].count(x)) ed[1].add(x[0], x[1]), ecol[x[1]].push_back(x[0]);
		ver.add(x[0], x[1]);
		//~ cout<<x[0]<<" "<<x[1]<<"\n";
		auto t = x; t[0]++, t[1]++;
		row[x[0]].push_back(x[1]);
		col[x[1]].push_back(x[0]);
	}
	
	ed[0].build();
	ed[1].build();
	ver.build();
	sq.build();
	for(int i=0;i<N;i++){
		sort(row[i].begin(), row[i].end());
		sort(col[i].begin(), col[i].end());
		sort(erow[i].begin(), erow[i].end());
		sort(ecol[i].begin(), ecol[i].end());
	}
}

/*

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

*/

ar<int, 2> get_r(int x, int l, int r){
	auto R = upper_bound(row[x].begin(), row[x].end(), r);
	auto L = lower_bound(row[x].begin(), row[x].end(), l);
	int v = R - L;
	r--;
	R = upper_bound(erow[x].begin(), erow[x].end(), r);
	L = lower_bound(erow[x].begin(), erow[x].end(), l);
	int e = R - L;
	return {v, e};
}


ar<int, 2> get_l(int x, int l, int r){
	auto R = upper_bound(col[x].begin(), col[x].end(), r);
	auto L = lower_bound(col[x].begin(), col[x].end(), l);
	int v = R - L;
	r--;
	R = upper_bound(ecol[x].begin(), ecol[x].end(), r);
	L = lower_bound(ecol[x].begin(), ecol[x].end(), l);
	int e = R - L;
	return {v, e};
}

int colour(int lx, int ly, int rx, int 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);
	auto t = get_r(lx, ly, ry + 1);
	//~ cout<<V<<" "<<ee<<endl;
	V += (ry - ly + 2 - t[0]);
	ee += (ry - ly + 1 - t[1]);
	
	t = get_r(rx + 1, ly, ry + 1);
	V += (ry - ly + 2 - t[0]);
	ee += (ry - ly + 1 - t[1]);
	
	t = get_l(ly, lx, rx + 1);
	V += (rx - lx + 2 - t[0]);
	ee += (rx - lx + 1 - t[1]);
	
	t = get_l(ry + 1, lx, rx + 1);
	V += (rx - lx + 2 - t[0]);
	ee += (rx - lx + 1 - t[1]);
	
	if(!tot.count({lx, ly})) V--;
	if(!tot.count({lx, ry + 1})) V--;
	if(!tot.count({rx + 1, ly})) V--;
	if(!tot.count({rx + 1, ry + 1})) V--;
	
	int F = sq.get(lx, rx, ly, ry);
	//~ cout<<V<<" "<<ee<<" "<<F<<"\n";
	return (2 - V + ee - F - 1);
}

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