Submission #1239566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239566		mychecksedad	The Big Prize (IOI17_prize)	C++20	20 / 100	23 ms	416 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define vi vector<int>
const int N = 2e5+100;

int n, T[2*N+5];
void build(int sz){
	for(int j = 0; j <= 2*sz + 5; ++j) T[j] = 0;
}
void add(int p){
	T[p += n]++;
	for(p >>= 1; p; p >>= 1) T[p] = T[p<<1] + T[p<<1|1]; 
}
int get(int l, int r){
	int res = 0;
	l += n;
	r += n + 1;
	for(; l < r; l >>= 1, r >>= 1){
		if(l&1) res += T[l++];
		if(r&1) res += T[--r];
	}
	return res;
}
int qq = 0;
vi askk(int x){
	qq++;
	if(qq > 9500) assert(false);
	return ask(x);
}
set<pii> X, Y;
int solve(int l, int r){
	int mid = l+r>>1;
	vi res = ask(mid);
	if(res[0] + res[1] == 0) return mid;
	vi resL = askk(l);
	vi resR = askk(r);

	res[0] -= resL[0];
	res[1] -= resR[1];

	// X.insert({mid, res[0]});
	// Y.insert({mid, res[1]});
	
	// auto it = Y.upper_bound(pii{mid, N});
	// if(it != Y.end()) res[1] -= (*it).ss;
	// auto it2 = X.upper_bound(pii{mid, -1});
	// if(it2 != X.begin()) res[0] -= (*prev(it2)).ss;

	// now we know what do we got in our boundary at least...

	if(res[0]){
		int x = solve(l, mid - 1);
		if(x != -1) return x;
	}
	if(res[1]){
		int x = solve(mid + 1, r);
		if(x != -1) return x;
	}
	return -1;
}


int find_best(int nn) {
	n = nn;
	return solve(0, n-1);
}

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