Submission #107389

#	Time	Username	Problem	Language	Result	Execution time	Memory
107389		Noam527	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1332 ms	118892 KiB

rainbow

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;

int countless(const vector<int> &a, int x) {
	if (!a.size()) return 0;
	int lo = 0, hi = (int)a.size() - 1, mid;
	while (lo < hi) {
		mid = (lo + hi) / 2;
		if (x <= a[mid]) hi = mid;
		else lo = mid + 1;
	}
	if (x > a[lo]) lo++;
	return lo;
}
int between(const vector<int> &a, int lo, int hi) {
	return countless(a, hi + 1) - countless(a, lo);
}
struct segtree {
	int n;
	vector<vector<int>> t;
	segtree() {}
	segtree(int sz) {
		n = max(2, sz);
		while (n != (n & -n)) n += (n & -n);
		t.resize(2 * n);
	}
	// sorted by .second
	void init(const vector<pair<int, int>> &a) {
		for (const auto &i : a)
			addpoint(i.first, i.second);
	}
	void addpoint(int x, int y) {
		x += n - 1;
		t[x].push_back(y);
		x = (x - 1) / 2;
		while (x) {
			t[x].push_back(y);
			x = (x - 1) / 2;
		}
		t[0].push_back(y);
	}
	void process() {
		for (auto &i : t)
			sort(i.begin(), i.end());
	}
	// x in [l, r], y in [lo, hi]
	int query(int l, int r, int lo, int hi) {
		if (l > r || lo > hi) return 0;
		int rtn = 0;
		for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) {
			if (!(l & 1)) rtn += between(t[l], lo, hi), l++;
			if (r & 1) rtn += between(t[r], lo, hi), r--;
		}
		if (l == r) rtn += between(t[l], lo, hi);
		return rtn;
	}
};

const int maxC = 200005;
segtree full(maxC), point(maxC), H(maxC), V(maxC);

bool cmp(const pair<int, int> &aa, const pair<int, int> &bb) {
	if (aa.second != bb.second) return aa.second < bb.second;
	return aa.first < bb.first;
}

int mn[2], mx[2];

void init(int R, int C, int sr, int sc, int M, char *S) {
	vector<pair<int, int>> a, b, c;
	a.emplace_back(sr, sc);
	mn[0] = mx[0] = sr;
	mn[1] = mx[1] = sc;
	for (int i = 0; i < M; i++) {
		if (S[i] == 'N') sr--;
		else if (S[i] == 'S') sr++;
		else if (S[i] == 'W') sc--;
		else sc++;
		mn[0] = min(mn[0], sr);
		mx[0] = max(mx[0], sr);
		mn[1] = min(mn[1], sc);
		mx[1] = max(mx[1], sc);
		a.emplace_back(sr, sc);
	}
	auto clean = [](vector<pair<int, int>> &aa) {
		sort(aa.begin(), aa.end(), cmp);
		aa.resize(unique(aa.begin(), aa.end()) - aa.begin());
	};
	clean(a);
	full.init(a);

	b.clear();
	b.reserve(4 * a.size());
	for (const auto &i : a) {
		b.emplace_back(i.first + 0, i.second + 0);
		b.emplace_back(i.first + 0, i.second + 1);
		b.emplace_back(i.first + 1, i.second + 0);
		b.emplace_back(i.first + 1, i.second + 1);
	}
	clean(b);
	point.init(b);

	b.clear();
	b.reserve(2 * a.size());
	c.reserve(2 * a.size());
	for (const auto &i : a) {
		b.emplace_back(i.first + 0, i.second + 0);
		c.emplace_back(i.first + 0, i.second + 0);
		b.emplace_back(i.first + 1, i.second + 0);
		c.emplace_back(i.first + 0, i.second + 1);
	}
	clean(b);
	clean(c);
	H.init(b);
	V.init(c);
	if (OO) {
		cout << "for V:\n";
		for (const auto &i : c) cout << i.first << " " << i.second << '\n';
		cout << V.query(3, 4, 3, 4) << '\n';
	}
}

int colour(int ar, int ac, int br, int bc) {
	if (ar < mn[0] && mx[0] < br && ac < mn[1] && mx[1] < bc)
		ar = mn[0];

	ll v = 0, e = 0;
	v += 2 * (br - ar + 1 + bc - ac + 1);
	v += point.query(ar + 1, br, ac + 1, bc);

	e += 2 * (br - ar + 1 + bc - ac + 1);
	e += H.query(ar + 1, br, ac, bc);
	e += V.query(ar, br, ac + 1, bc);

	if (OO) cout << "v: " << v << '\n';
	if (OO) cout << "e: " << e << '\n';
	if (OO) cout << "full: " << full.query(ar, br, ac, bc) << '\n';
	if (OO) cout << "H: " << H.query(ar + 1, br, ac, bc) << '\n';
	if (OO) cout << "V: " << V.query(ar, br, ac + 1, bc) << '\n';

	return e - v + 1 - full.query(ar, br, ac, bc);
}
/*
int main() {
	int R, C, sr, sc, n;
	cin >> R >> C >> sr >> sc >> n;
	char *S = new char[n];
	cin >> S;
	init(R, C, sr, sc, n, S);
	while (1) {
		int ar, ac, br, bc;
		cout << "top left: ";
		cin >> ar >> ac;
		cout << "bottom right: ";
		cin >> br >> bc;
		cout << colour(ar, ac, br, bc) << '\n';
	}
}
*/

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