#include "lottery.h"
#include<bits/stdc++.h>
using namespace std;
//#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native,sse,sse2,sse3")
using namespace std;
#define int long long
const int mxn=2e5,minf=-1e18,Mx=1e4,inf=1e18;
int x[mxn+10],y[mxn+10],n,q;
int prefx[mxn+10],prefy[mxn+10];
struct seg{
int v[2*mxn+10];
void init(){for(int i=0;i<=2*n;i++)v[i]=inf;}
void update(int pos,int val){
pos+=n;
v[pos]=val;
for(int i=pos;i>0;i>>=1)v[i>>1]=min(v[i],v[i^1]);
}
int qry(int l,int r){
int ans=inf;
for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
if(l&1)ans=min(ans,v[l++]);
if(!(r&1))ans=min(ans,v[r--]);
}
return ans;
}
}t;
struct node{
node *l,*r;
int sum,cnt;
node():sum(0),l(0),r(0),cnt(0){}
};
node *rootx[mxn+10];
node *rooty[mxn+10];
int getsum(node *cur){
if(cur==NULL)return 0;
return cur->sum;
}
int getcnt(node *cur){
if(cur==NULL)return 0;
return cur->cnt;
}
int getsumL(node *cur){
if(cur==NULL)return 0;
return cur->sum-getsum(cur->r);
}
int getsumR(node *cur){
if(cur==NULL)return 0;
return getsum(cur->r);
}
int getcntL(node *cur){
if(cur==NULL)return 0;
return cur->cnt-getcnt(cur->r);
}
int getcntR(node *cur){
if(cur==NULL)return 0;
return getcnt(cur->r);
}
void update(node *&cur,node *lcur,int pos,int l=0,int r=2e9){
if(lcur==NULL)cur=new node();
else cur=new node(*lcur);
if(l==r){
cur->sum+=pos;
cur->cnt++;
return;
}
int mid=l+(r-l)/2;
if(pos<=mid)update(cur->l,(lcur==NULL)? NULL:lcur->l,pos,l,mid);
else update(cur->r,(lcur==NULL)? NULL:lcur->r,pos,mid+1,r);
cur->sum=getsum(cur->l)+getsum(cur->r);
cur->cnt=getcnt(cur->l)+getcnt(cur->r);
}
void init(int32_t N, int32_t Q, vector<int32_t> X, vector<int32_t> Y){
n=N;
q=Q;
t.init();
for(int i=1;i<=n;i++){
x[i]=X[i-1],y[i]=Y[i-1];
update(rootx[i],rootx[i-1],x[i]);
update(rooty[i],rooty[i-1],y[i]);
t.update(i,x[i]+y[i]);
}
}
node *getL(node *cur){
if(cur==NULL)return NULL;
return cur->l;
}
node *getR(node *cur){
if(cur==NULL)return NULL;
return cur->r;
}
int solve(node *LX,node *RX,node *LY,node *RY,pii a,pii b,int sz,int mn,int l=0,int r=2e9){
int mid=l+(r-l)/2;
if(RX==NULL&&RY==NULL){
int ans=0;
int ll=l,rr=min(r,mn);
while(ll<=rr){
int M=ll+(rr-ll)/2;
if((M*b.f)+b.s<=M*sz&&M*sz<=(M*a.f)+a.s)ll=M+1,ans=max(ans,M);
else rr=M-1;
}
return ans;
}
if(mid>mn){
if(l==r)return 0;
return solve(getL(LX),getL(RX),getL(LY),getL(RY),{a.f+getcntR(RX)-getcntR(LX),a.s},b,sz,mn,l,mid);
}
int cr=(mid*a.f)+a.s,cl=(mid*b.f)+b.s;
int need=mid*sz;
cr+=getsumL(RX)-getsumL(LX)+mid*(getcntR(RX)-getcntR(LX));
cl+=mid*(getcntL(RY)-getcntL(LY))-(getsumL(RY)-getsumL(LY));
if(cl<=need&&need<=cr){
if(l==r)return mid;
return max(mid,solve(getR(LX),getR(RX),getR(LY),getR(RY),
{a.f,a.s+getsumL(RX)-getsumL(LX)},
{b.f+getcntL(RY)-getcntL(LY),b.s-(getsumL(RY)-getsumL(LY))},
sz,mn,mid+1,r
));
}
else{
if(l==r)return 0;
return solve(getL(LX),getL(RX),getL(LY),getL(RY),{a.f+getcntR(RX)-getcntR(LX),a.s},b,sz,mn,l,mid);
}
}
int32_t max_prize(int32_t L, int32_t R){
L++,R++;
return solve(rootx[L-1],rootx[R],rooty[L-1],rooty[R],{0,0},{0,0},(R-L+1)/2,t.qry(L,R));
}
/*
5 3
2 1 3 1 0
1 1 0 2 0
0 3
1 4
2 3
6 5
1 3 3 2 1 0
1 2 1 1 2 1
0 1
1 2
1 4
2 5
4 5
*/
