Submission #536369

#	Time	Username	Problem	Language	Result	Execution time	Memory
536369		lunchbox	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1161 ms	167560 KiB

rainbow

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

#define N	200005
#define L	18
#define N_	(1 << L)
#define M	(42424242)

int sum[M], ll[M], rr[M];

int node(int k = 0) {
	static int _ = 1;
 
	sum[_] = sum[k];
	ll[_] = ll[k], rr[_] = rr[k];
	return _++;
}
 
int build_(int l, int r) {
	int v = node(), m;
 
	if (l < r) {
		m = (l + r) / 2;
		ll[v] = build_(l, m);
		rr[v] = build_(m + 1, r);
	}
	return v;
}
 
int update(int v, int l, int r, int i) {
	int v_ = node(v), m;
 
	sum[v_]++;
	if (l < r) {
		m = (l + r) / 2;
		if (i <= m)
			ll[v_] = update(ll[v], l, m, i);
		else
			rr[v_] = update(rr[v], m + 1, r, i);
	}
	return v_;
}
int query_(int v, int l, int r, int ql, int qr) {
	int m;
 
	if (qr < l || ql > r)
		return 0;
	if (ql <= l && qr >= r)
		return sum[v];
	m = (l + r) / 2;
	return query_(ll[v], l, m, ql, qr) + query_(rr[v], m + 1, r, ql, qr);
}

struct tree {
	vector<int> pp[N + 1];
	int xx[N + 1];

	void add(int i, int j) {
		pp[i].push_back(j);
	}
	void build() {
		for (int i = 1; i <= N; i++) {
			xx[i] = xx[i - 1];
			sort(pp[i].begin(), pp[i].end());
			pp[i].erase(unique(pp[i].begin(), pp[i].end()), pp[i].end());
			for (int j : pp[i - 1])
				xx[i] = update(xx[i], 1, N, j);
		}
	}
	int query(int i, int j, int i_, int j_) {
		if (i_ > j_)
			return 0;
		return query_(xx[j + 1], 1, N, i_, j_) - query_(xx[i], 1, N, i_, j_);
	}
} st0, st1, st2, st3;
 
void add(int i, int j) {
	st0.add(i, j);
	st0.add(i + 1, j);
	st0.add(i, j + 1);
	st0.add(i + 1, j + 1);
	st1.add(i, j);
	st1.add(i + 1, j);
	st2.add(i, j);
	st2.add(i, j + 1);
	st3.add(i, j);
}

int mx_i, mn_i, mx_j, mn_j;

void init(int n, int m, int si, int sj, int k, char *s) {
	add(si, sj);
	mx_i = mn_i = si;
	mx_j = mn_j = sj;
	for (int i = 0; i < k; i++) {
		if (s[i] == 'N')
			si--;
		if (s[i] == 'E')
			sj++;
		if (s[i] == 'S')
			si++;
		if (s[i] == 'W')
			sj--;
		add(si, sj);
		mx_i = max(mx_i, si);
		mn_i = min(mn_i, si);
		mx_j = max(mx_j, sj);
		mn_j = min(mn_j, sj);
	}
	st0.build();
	st1.build();
	st2.build();
	st3.build();
}

int colour(int i, int j, int i_, int j_) {
	int E = st1.query(i + 1, i_, j, j_) + st2.query(i, i_, j + 1, j_);
	int V = st0.query(i + 1, i_, j + 1, j_);
	int R = st3.query(i, i_, j, j_);
	int C = (i >= mn_i || i_ <= mx_i || j >= mn_j || j_ <= mx_j ? 1 : 2);
	return E - V + C - R;
}

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