#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
struct pii{int a, b;};
typedef vector<int> vi;
vi getVal(int i, map<int, vi>& cache) {
if(cache.count(i)) return cache[i];
return cache[i] = ask(i);
}
void getBetter(int l, int r, int loid, int lOff, int rOff, map<int, vi>& cache) {
assert(l <= r);
int mid = (l + r) / 2;
REP(ci, mid, r+1) {
vi cv = getVal(ci, cache);
if(cv[0] + cv[1] == loid) {
if(cv[0] + lOff > 0) getBetter(l, ci - 1, loid, lOff, -cv[1], cache);
if(cv[1] + rOff > 0) getBetter(ci+1, r, loid, -cv[0], rOff, cache);
return;
}
}
for(int ci = mid - 1; ci >= l; --ci) {
vi cv = getVal(ci, cache);
if(cv[0] + cv[1] == loid) {
if(cv[0] + lOff > 0) getBetter(l, ci - 1, loid, lOff, -cv[1], cache);
if(cv[1] + rOff > 0) getBetter(ci+1, r, loid, -cv[0], rOff, cache);
return;
}
}
}
const int MV = 450;
int find_best(int n){
map<int, vi> ca;
forR(i, min(n, MV)) getVal(i, ca);
int loVal = ca[0][0] + ca[0][1];
forR(i, min(n, MV)) loVal = max(loVal, ca[i][0] + ca[i][1]);
getBetter(0, n-1, loVal, 0, 0, ca);
int bi = -1;
for(auto [ci, cv] : ca) if(cv[0] + cv[1] == 0) {
bi = ci;
}
assert(bi != -1);
return bi;
}
Compilation message
prize.cpp: In function 'vi getVal(int, std::map<int, std::vector<int> >&)':
prize.cpp:10:23: error: 'ask' was not declared in this scope
10 | return cache[i] = ask(i);
| ^~~
