#include "lottery.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
ll v2(ll x) {
if (x==0) {
return 100;
}
return __builtin_ctz(x);
}
ll l2(ll x) {
if (x==0) {
return 100;
}
return (31-__builtin_clz(x));
}
pii operator+(const pii& l, const pii& r) {
return (pii) {l.first+r.first,l.second+r.second};
}
struct Node {
Node *l=nullptr, *r=nullptr;
ll xl=0,xr=(1LL<<31)-1;
pii pa={0LL,0LL}, pb={0LL,0LL}; //number/sum red/blue ("a/b")
Node() {
xl = 0; xr = (1LL<<31)-1;
}
Node(ll _xl, ll _xr) {
xl = _xl; xr = _xr;
}
pii lpa() {
if (l==nullptr) {
return {0LL,0LL};
} else {
return l->pa;
}
}
pii lpb() {
if (l==nullptr) {
return {0LL,0LL};
} else {
return l->pb;
}
}
void upd(ll v, bool isa) { //increase at value v
if (v<xl || v>xr) {
return;
}
assert(xl<=v && v<=xr);
//cerr << "xl="<<xl<<", xr="<<xr<<"\n";
if (xl==xr) {
assert(xl==v);
if (isa) {
pa = {pa.first+1,pa.second+v};
} else {
pb = {pb.first+1,pb.second+v};
}
return;
}
ll m = (xl+xr)/2;
if (v<=m) {
if (l==nullptr) {
l = new Node(xl,m);
}
l->upd(v,isa);
} else {
if (r==nullptr) {
r = new Node(m+1,xr);
}
r->upd(v,isa);
}
if (isa) {
pa = {pa.first+1,pa.second+v};
} else {
pb = {pb.first+1,pb.second+v};
}
return;
}
};
const ll Nm = 262144; const ll E = 18;
ll stmn[2*Nm]; //segtree of min numbers (total capacity)
Node* st[2*Nm];
ll qrmn(ll l, ll r) {
if (l>r) {
return (1LL<<31); //infinity
}
ll vl = v2(l); ll vr = v2(r+1);
if (vl<vr) {
return min(qrmn(l+(1LL<<vl),r),stmn[(l>>vl)+(1LL<<(E-vl))]);
} else {
return min(qrmn(l,r-(1LL<<vr)),stmn[(r>>vr)+(1LL<<(E-vr))]);
}
}
void plst(ll i, ll x, ll y) {
ll p = i+Nm;
stmn[p]=x+y;
st[p]->upd(x,0);
st[p]->upd(y,1);
p=p/2;
do {
stmn[p]=min(stmn[2*p],stmn[2*p+1]);
st[p]->upd(x,0);
st[p]->upd(y,1);
p=p/2;
} while (p>0);
}
void init(int N, int Q, vector<int> X, vector<int> Y) {
for (ll i=0;i<N;i++) {
plst(i,X[i],Y[i]);
}
}
int max_prize(int l, int r) {
ll l1=l; ll r1=r;
vector<Node*> vn;
while (l1<=r1) {
ll vl = v2(l1); ll vr = v2(r1+1);
if (vl<vr) {
vn.push_back(st[(l1>>vl)+(1LL<<(E-vl))]);
l1 += (1LL<<vl);
} else {
vn.push_back(st[(r1>>vr)+(1LL<<(E-vr))]);
r1 -= (1LL<<vr);
}
}
ll K = vn.size();
ll xl = 0; ll xr = (1LL<<31)-1;
pii pta={0LL,0LL}, ptb={0LL,0LL};
while (xl<xr) { //searching for: smallest one that DOES NOT work
ll xm = (xl+xr)/2;
pii pna=pta, pnb=ptb;
for (ll k=0;k<K;k++) {
if (vn[k]!=nullptr) {
pna = pna + (vn[k]->lpa());
pnb = pnb + (vn[k]->lpb());
}
}
ll vla = (r-l+1-pna.first)*xm+pna.second;
ll vlb = (r-l+1-pnb.first)*xm+pnb.second;
ll vt = ((r-l+1)/2)*xm;
if (vla>=vt && vlb>=vt) {
//pass: go right
pta = pna; ptb = pnb;
xl = xm+1;
for (ll k=0;k<K;k++) {
if (vn[k]!=nullptr) {
vn[k]=vn[k]->r;
}
}
} else {
//fail: go left
xr = xm;
for (ll k=0;k<K;k++) {
if (vn[k]!=nullptr) {
vn[k]=vn[k]->l;
}
}
}
}
return min((xl-1),qrmn(l,r));
}
