Submission #683827

#	Time	Username	Problem	Language	Result	Execution time	Memory
683827		S2speed	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	882 ms	193288 KiB

rainbow

#include "rainbow.h"
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (int)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cout<<"--------------------------------------\n";
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 2e5 + 17 , md = 1e9 + 7 , inf = 2e8;

vector<int> merge(vector<int> &a , vector<int> &b){
	vector<int> res;
	int as = sze(a) , bs = sze(b);
	a.push_back(inf); b.push_back(inf);
	int x = 0 , y = 0;
	for(int e = 0 ; e < as + bs ; e++){
		if(a[x] < b[y]){
			res.push_back(a[x++]);
		} else {
			res.push_back(b[y++]);
		}
	}
	a.pop_back(); b.pop_back();
	return res;
}

struct segtree {

	int sz = 1;
	vector<vector<int>> val;

	void init(int n){
		while(sz < n) sz <<= 1;
		val.resize(sz << 1);
		return;
	}

	void add(int i , int k , int x , int lx , int rx){
		if(rx - lx == 1){
			val[x].push_back(k);
			return;
		}
		int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		if(i < m){
			add(i , k , ln , lx , m);
		} else {
			add(i , k , rn , m , rx);
		}
		return;
	}

	void add(int i , int k){
		add(i , k , 0 , 0 , sz);
		return;
	}

	void build(int x , int lx , int rx){
		if(rx - lx == 1){
			sort(all(val[x]));
			val[x].resize(distance(val[x].begin() , unique(all(val[x]))));
			return;
		}
		int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		build(ln , lx , m); build(rn , m , rx);
		val[x] = merge(val[ln] , val[rn]);
		return;
	}

	void build(){
		build(0 , 0 , sz);
		return;
	}

	int cal(int l1 , int r1 , int l2 , int r2 , int x , int lx , int rx){
		if(rx <= l1 || lx >= r1) return 0;
		if(rx <= r1 && lx >= l1){
			int res = lower_bound(all(val[x]) , r2) - lower_bound(all(val[x]) , l2);
			return res;
		}
		int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		int a = cal(l1 , r1 , l2 , r2 , ln , lx , m) , b = cal(l1 , r1 , l2 , r2 , rn , m , rx);
		return a + b;
	}

	int cal(int l1 , int r1 , int l2 , int r2){
		return cal(l1 , r1 , l2 , r2 , 0 , 0 , sz);
	}

};

segtree v , e[2] , f;
vector<int> vx[maxn] , vy[maxn];

void add(int x , int y){
	v.add(x , y);
	e[0].add(x - 1 , y); e[0].add(x , y);
	e[1].add(x , y - 1); e[1].add(x , y);
	f.add(x - 1 , y - 1); f.add(x - 1 , y); f.add(x , y - 1); f.add(x , y);
	vx[x].push_back(y); vy[y].push_back(x);
	return;
}

void init(int n , int m , int sx , int sy , int k , char *s){
	v.init(n + 1); e[0].init(n + 1); e[1].init(n + 1); f.init(n + 1);
	int x = sx , y = sy;
	for(int i = 0 ; ; i++){
		add(x , y);
		if(i == k) break;
		if(s[i] == 'N'){
			x--;
		} else if(s[i] == 'S'){
			x++;
		} else if(s[i] == 'E'){
			y++;
		} else {
			y--;
		}
	}
	for(int i = 1 ; i <= n ; i++){
		sort(all(vx[i]));
	}
	for(int i = 1 ; i <= m ; i++){
		sort(all(vy[i]));
	}
	v.build(); e[0].build(); e[1].build(); f.build();
	return;
}

bool mohit(int x1 , int y1 , int x2 , int y2){
	int res = 0;
	res += lower_bound(all(vx[x1]) , y2) - lower_bound(all(vx[x1]) , y1);
	res += lower_bound(all(vx[x2 - 1]) , y2) - lower_bound(all(vx[x2 - 1]) , y1);
	res += lower_bound(all(vy[y1]) , x2) - lower_bound(all(vy[y1]) , x1);
	res += lower_bound(all(vy[y2 - 1]) , x2) - lower_bound(all(vy[y2 - 1]) , x1);
	return (res > 0);
}

int colour(int l1 , int l2 , int r1 , int r2){
	r1++; r2++;
	ll h = v.cal(l1 , r1 , l2 , r2);
	if(h == 0) return 1;
	ll V = 1ll * (r1 - l1) * (r2 - l2) - h;
	ll E = 1ll * (r1 - l1) * (r2 - l2 - 1) + 1ll * (r1 - l1 - 1) * (r2 - l2);
	E -= e[0].cal(l1 , r1 - 1 , l2 , r2) + e[1].cal(l1 , r1 , l2 , r2 - 1);
	ll F = 1ll * (r1 - l1 - 1) * (r2 - l2 - 1) - f.cal(l1 , r1 - 1 , l2 , r2 - 1) + 1 + !mohit(l1 , l2 , r1 , r2);
	return V - E + F - 1;
}

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