Submission #415412

#	Time	Username	Problem	Language	Result	Execution time	Memory
415412		SeDunion	The Big Prize (IOI17_prize)	C++17	100 / 100	155 ms	24640 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 55;
 
const int K = N/455;
 
vector<int>memo[N]; int done[N];
 
int Q;
 
set<int>alive;
 
void del(int l, int r) {
	while (alive.size()) {
		auto it = alive.lower_bound(l);
		if (it == alive.end()) break;
		if (*it <= r) alive.erase(it);
		else break;
	}
}
 
set<int>pos[N];
 
vector<int>qwe(int i) {
	if (done[i]) return memo[i];
	done[i] = 1; memo[i] = ask(i);
	int x = memo[i][0] + memo[i][1];
	if (x == 0) return memo[i];
	{
		auto it = pos[x].lower_bound(i);
		if (it == pos[x].end() && memo[i][1] == 0) del(i, N);
		if (it != pos[x].end() && memo[i][1] == memo[*it][1]) del(i, *it);
		if (it == pos[x].begin() && memo[i][0] == 0) del(0, i);
		if (it != pos[x].begin() && memo[i][0] == memo[*prev(it)][0]) del(*prev(it), i);
		pos[x].insert(i);
	}
	return memo[i];
}
 
int solve(int need, int ql, int qr, int mx) {
	if (ql > qr) return -1;
	int l = ql, r = qr, ret = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		auto it = alive.lower_bound(mid);
		int m = -1;
		if (it != alive.end() && *it <= r) m = *it;
		else if (it != alive.begin() && *prev(it) >= l && *prev(it) <= r) m = *prev(it);
		else break;
		if (qwe(m)[0] + qwe(m)[1] == 0) return m;
		if (qwe(m)[0] + qwe(m)[1] != mx) ret = m, r = m - 1;
		else if (qwe(m)[0] == need) l = m + 1;
		else r = m - 1;
	}
	if (ret == -1) return -1;
	r = ret;
	while (r <= qr) {
		//if (alive.count(r) == 0) {
		//	r++;
		//	continue;
		//}
		if (qwe(r)[0] + qwe(r)[1] == 0) return r;
		if (qwe(r)[0] + qwe(r)[1] == mx) break;
		++r;
	}
	return solve(qwe(r)[0], r, qr, mx);
}
 
int find_best(int n) {
	for (int i = 0 ; i < n ; ++ i) alive.insert(i);
	//if (n <= 10000) {
		//for (int i = 0 ; i < n ; ++ i) {
			//if (alive.count(i) == 0) continue;
			//if (qwe(i)[0] + qwe(i)[1] == 0) return i;
		//}
	//}
	vector<int>ids;
	int mx = 0;
	for (int i = 0 ; i < n - 1 ; i += K) {
		if (qwe(i)[0] + qwe(i)[1] == 0) return i;
		mx = max(mx, qwe(i)[0] + qwe(i)[1]);
		ids.emplace_back(i);
	}
	if (qwe(n - 1)[0] + qwe(n - 1)[1] == 0) return n - 1;
	mx = max(mx, qwe(n-1)[0] + qwe(n-1)[1]);
	ids.emplace_back(n - 1);
	for (int i = 0 ; i + 1 < (int)ids.size() ; ++ i) {
		int x = ids[i], y = ids[i + 1];
		while (x <= y) {
			if (qwe(x)[0] + qwe(x)[1] == 0) return x;
			if (qwe(x)[0] + qwe(x)[1] == mx) break;
			++x;
		}
		while (x <= y) {
			if (qwe(y)[0] + qwe(y)[1] == 0) return y;
			if (qwe(y)[0] + qwe(y)[1] == mx) break;
			--y;
		}
		if (x > y) continue;
		int res = solve(qwe(x)[0], x, y, mx);
		if (res != -1) return res;
	}
	return -1;
}

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80