Submission #433507

#	Time	Username	Problem	Language	Result	Execution time	Memory
433507		rqi	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1827 ms	459240 KiB

rainbow

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

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define ins insert
#define pb push_back

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

void ckmin(int& a, int b){
	a = min(a, b);
}

void ckmax(int& a, int b){
	a = max(a, b);
}

vector<char> dchar = vector<char>{'S', 'E', 'N', 'W'};
vi dx = vi{1, 0, -1, 0};
vi dy = vi{0, 1, 0, -1};

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

struct hashFunc{
	size_t operator()(pi a) const {
		ll res = ll(a.f)*200005+ll(a.s);
		ll BIG_RAND = 102923014203249LL;
		return __builtin_bswap64((unsigned long long)(res)*BIG_RAND);
	}
};

const int mx = 200005;

struct node{
	ll val;
	node* c[2];

	node(){
		val = 0;
		c[0] = c[1] = NULL;
	}

	void pull(){
		val = 0;
		for(int i = 0; i < 2; i++){
			if(c[i]){
				val+=c[i]->val;
			}
		}
	}
};

const int SZ = 262144;

node* build(int L = 0, int R = SZ-1){
	node* a = new node();
	if(L == R){
		return a;
	}
	int M = (L+R)/2;
	a->c[0] = build(L, M);
	a->c[1] = build(M+1, R);
	return a;
}

node* upd(node* cur, int pos, int L = 0, int R = SZ-1){

	assert(cur);


	node* res = new node();

	*res = *cur;

	if(L == R){
		res->val++;
		return res;
	}


	assert(cur->c[0]);
	assert(cur->c[1]);

	int M = (L+R)/2;

	if(pos <= M){
		res->c[0] = upd(cur->c[0], pos, L, M);
	}
	else{
		res->c[1] = upd(cur->c[1], pos, M+1, R);
	}
	res->pull();
	return res;
}

ll query(node* cur, int l, int r, int L = 0, int R = SZ-1){
	if(r < L || R < l) return 0;

	if(l <= L && R <= r){
		return cur->val;
	}

	int M = (L+R)/2;

	return query(cur->c[0], l, r, L, M)+query(cur->c[1], l, r, M+1, R);
}

struct Off2DBIT{
	node* seg[mx];

	vpi all_updates;
	void update(int X, int Y){
		all_updates.pb(mp(X, Y));
	}


	void initBT(){
		// cout << "all_updates: " << "\n";
		// for(const auto& u: all_updates){
		// 	cout << u.f << " " << u.s << "\n";
		// }
		seg[0] = build();

		for(auto &u: all_updates){
			swap(u.s, u.f);
		}


		sort(all(all_updates));

		int cur_ind = 0;


		for(int i = 1; i < mx; i++){
			seg[i] = seg[i-1];
			while(cur_ind < sz(all_updates)){
				assert(all_updates[cur_ind].f >= i);
				if(all_updates[cur_ind].f > i) break;
				seg[i] = upd(seg[i], all_updates[cur_ind].s);
				cur_ind++; 
			}
		}
	}

	ll query(int xl, int yl, int xr, int yr){
		return ::query(seg[yr], xl, xr)-::query(seg[yl-1], xl, xr);
	}

	// ll query(int xl, int yl, int xr, int yr){
	// 	ll res = 0;
	// 	for(auto& u: all_updates){
	// 		if(xl <= u.f && u.f <= xr && yl <= u.s && u.s <= yr){
	// 			res++;
	// 		}
	// 	}
	// 	return res;
	// }
};

Off2DBIT bits[2][2];
gp_hash_table<pi, null_type, hashFunc> rects[4];

int min_sr, max_sr, min_sc, max_sc;

void init(int R, int C, int sr, int sc, int M, char *S) {
	min_sr = sr;
	min_sc = sc;
	max_sr = sr;
	max_sc = sc;
	for(int i = 0; i <= M; i++){
		for(int i = 0; i <= 1; i++){
			for(int j = 0; j <= 1; j++){
				for(int xl = sr-i; xl <= sr; xl++){
					for(int yl = sc-j; yl <= sc; yl++){
						if(1 <= xl && 1 <= yl){
							rects[2*i+j][mp(xl, yl)];
						}
					}
				}
			}
		}
		if(i < M){
			for(int d = 0; d < 4; d++){
				if(S[i] == dchar[d]){
					sr+=dx[d];
					sc+=dy[d];
					break;
				}
			}
		}

		ckmin(min_sr, sr);
		ckmin(min_sc, sc);
		ckmax(max_sr, sr);
		ckmax(max_sc, sc);
	}

	for(int i = 0; i <= 1; i++){
		for(int j = 0; j <= 1; j++){
			// cout << "i, j = " << i << ", " << j << "\n";
			for(auto u: rects[2*i+j]){
				// cout << "RECT " << i << " " << j << " " << u.f << " " << u.s << "\n";
				bits[i][j].update(u.f, u.s);
			}
		}
	}

	for(int i = 0; i <= 1; i++){
		for(int j = 0; j <= 1; j++){
			bits[i][j].initBT();
		}
	}

}

int colour(int ar, int ac, int br, int bc) {
	ll ans = 0;
	if(ar+1 <= min_sr && max_sr+1 <= br && ac+1 <= min_sc && max_sc+1 <= bc){
		ans++;
	}
	
	for(int i = 0; i <= 1; i++){
		for(int j = 0; j <= 1; j++){
			ll val = ll(br-i-ar+1)*ll(bc-j-ac+1);
			// cout << "val: " << val << "\n";
			// cout << "querying " << i << " " << j << "\n";
			val-=bits[i][j].query(ar, ac, br-i, bc-j);
			if((i+j) % 2 == 0){
				ans+=val;
			}
			else{
				ans-=val;
			}

			// cout << i << " " << j << " " << val << "\n";
		}
	}
    return (int)(ans);
}

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