Submission #334742

#	Time	Username	Problem	Language	Result	Execution time	Memory
334742		LucaDantas	The Big Prize (IOI17_prize)	C++17	0 / 100	23 ms	13164 KiB

prize

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

constexpr int maxn = 2e5;

const vector<int> good = {0, 0};

struct BIT
{
	int bit[maxn];

	void build() {
		for(int i = 1; i < maxn; i++)
			bit[i] = i&-i;
	}

	void upd(int x, int v) {
		for(x++; x < maxn; x += x&-x)
			bit[x] += v;
	}

	int query(int x) {
		int ans = 0;
		for(x++; x > 0; x -= x&-x)
			ans += bit[x];
		return ans;
	}

	int bs(int x) {
		int pos = 0;
		for(int l = 20; l >= 0; l--) {
			if(pos + (1 << l) >= maxn) continue;
			if(bit[pos + (1 << l)] < x)
				pos += (1 << l), x -= bit[pos];
		}
		return pos;
	}
} bit1, bit2;

// int cnt;

vector<int> val[maxn];

int rmv[maxn];

int find_best(int n) {
	bit1.build();
	int base = 0;
	for(int i = 0; i < min(n, 475); i++) {
		vector<int> a = ask(i);
		base = max(base, a[0]+a[1]);
	}

	set<int> st;
	int qtd = 1;
	while(1) {
		int l = 0, r = n-qtd;
		while(l <= r) {
			int m = (l+r) >> 1;
			int pos = bit1.bs(m);
			assert(!rmv[pos]);
			rmv[pos] = 1;
			// printf("pos qtd %d %d\n", pos, qtd);
			++qtd;
			bit1.upd(pos, -1);
			vector<int> a = ask(pos);
			val[pos] = a;
			auto it = st.upper_bound(pos);
			if(it != st.end()) {
				// assert(*it > pos);
				// printf("next it %d\n", *it);
				if((val[(*it)][0] - val[pos][0]) == 0) {
					for(int i = pos+1; i < *it; ++i)
						/*assert(!rmv[i]), */bit1.upd(i, -1), ++qtd, rmv[i] = 1;
				}
			}
			if(it != st.begin()) {
				--it;
				// assert(*it < pos);
				// printf("last it %d\n", *it);
				if((val[pos][0] - val[(*it)][0]) == 0) {
					for(int i = (*it)+1; i < pos; ++i)
						/*assert(!rmv[i]), */bit1.upd(i, -1), ++qtd, rmv[i] = 1;
				}
			}
			st.insert(pos);
			// assert(++cnt < 10);
			if(a == good) return pos;
			if(a[0]+a[1] == base) {
				if(a[0]-bit2.query(pos)) r = m-1;
				else l = m+1;
			} else {
				bit2.upd(pos, 1);
				break;
			}
			r = min(r, n-qtd);
		}
	}
}

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