#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
// ask
struct MY{
set < pair < int, int > > L, R;
MY() {
L.insert({0, 0});
R.insert({200200, 0});
}
void add_l(int pos, int val) {
L.insert({pos, val});
}
void add_r(int pos, int val) {
R.insert({pos, val});
}
int find_l(int m) {
return prev(L.upper_bound({m, 0}))->second;
}
int find_r(int m) {
return R.upper_bound({m - 1, 200200})->second;
}
};
map < int, pair < int, int > > mp;
map < int, MY > cnt;
pair < int, int > check(int i) {
auto it = mp.find(i);
if(it != mp.end()) {
return it->second;
}
mp[i];
it = mp.find(i);
auto res = ask(i - 1);
it->second = {res[0], res[1]};
return it->second;
}
int recur(int l, int r) {
int m = (l + r) / 2;
auto [a, b] = check(m);
if(a + b < 2) {
return m;
}
int c = a + b;
auto it = cnt.find(c);
if(it == cnt.end()) {
cnt[c];
it = cnt.find(c);
}
int x = a, y = b;
a -= it->second.find_l(l);
b -= it->second.find_r(r);
it->second.add_l(m - 1, x);
it->second.add_r(m + 1, y);
if(a > b) {
return recur(l, m);
}
return recur(m, r);
}
int find_best(int n) {
int l = 0, r = n + 1, m;
mp[l] = {0, 0};
mp[r] = {0, 0};
for(;;) {
m = recur(l, r);
auto [a, b] = check(m);
if(a|b) {
(a ? r : l) = m;
} else {
break;
}
}
return m - 1;
}
Compilation message
simurgh.cpp:1:10: fatal error: prize.h: No such file or directory
1 | #include "prize.h"
| ^~~~~~~~~
compilation terminated.
