#include "lottery.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pb push_back
#define mp make_pair
#define lsb(x) (x&(-x))
#define pii pair<int,int>
#define ss second
#define ff first
#define piii pair<int,pii>
#define debu(x) (cerr << #x << " = "<< x << "\n")
#define debu2(x,y) {(cerr << #x << " = "<< x << " " << #y << " = " << y << "\n");cerr.flush();}
#define debu3(x,y,z) (cerr << #x << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n")
#define bitout(x,y) {\
cerr << #x << " : ";\
for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\
cout << "\n";\
}
#define rangeout(j,rangestart,rangeend) {\
cerr << "outputting " << #j<< ":\n";\
for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\
cerr<<"\n";\
}
#define c1 {cerr << "Checkpoint 1! \n\n";cerr.flush();}
#define c2 {cerr << "Checkpoint 2! \n\n";cerr.flush();}
#define c3 {cerr << "Checkpoint 3! \n\n";cerr.flush();}
#define c4 {cerr << "Checkpoint 4! \n\n";cerr.flush();}
//bin search upper limit too small :(
//UGH THE INPUT IS ONE INDEXEDED EQF)NEF)EF
typedef long long ll;
ll n;
vector<ll>reds,blues;
map<ll,ll>corr;
vector<ll>revcorr;
vector<ll>sg;
struct Node
{
ll s,e,m,val1=0,val2=0,cnt1=0,cnt2=0;
Node *l=NULL,*r=NULL;
Node(int star, int en)
{
s=star;e=en;
m=(s+e)/2;
}
Node* update(int pos, bool forred)
{
Node* xin=new Node(s,e);
xin->val1=val1;xin->val2=val2;xin->cnt1=cnt1;xin->cnt2=cnt2;
if(forred){xin->val1+=revcorr[pos];xin->cnt1++;}
else {xin->val2+=revcorr[pos];xin->cnt2++;}
if(pos==s&&pos==e){return xin;}
if(pos<=m)
{
if(l==nullptr)l=new Node(s,m);
xin->l=(l->update(pos,forred));
xin->r=r;
}
else
{
if(r==nullptr)r=new Node(m+1,e);
xin->r=(r->update(pos,forred));
xin->l=l;
}
return xin;
}
pii query(bool forred, int reqs, int reqe)
{
//debu2(s,e);
if(reqs>reqe)return mp(0,0);
if(reqs<=s&&reqe>=e)
{
if(forred){return mp(cnt1,val1);}
else{return mp(cnt2,val2);}
}
pii retno=mp(0,0);
if(reqs<=m&&l!=nullptr)
{
pii t1=l->query(forred,reqs,reqe);
retno=t1;
}
if(reqe>m&&r!=nullptr)
{
pii t2=r->query(forred,reqs,reqe);
retno.ff+=t2.ff;retno.ss+=t2.ss;
}
return retno;
}
};
vector<Node*>preffys;
bool checkers(ll lsz, ll x, Node *s, Node *e)
{
//debu2(s->val1,e->val1);
ll ni=x*lsz/2;
auto k=corr.lower_bound(x);
int y;
if(k==corr.end())y=revcorr.size()-1;
else y=revcorr[(*k).ss];y--;
pii t1=s->query(0,0,y);
pii t2=e->query(0,0,y);
int forblue=t2.ss-t1.ss;
forblue+=x*(lsz-(t2.ff-t1.ff));
//debu3(forblue,t1.ff,t1.ss);
//debu3(x,t2.ff,t2.ss);
t1=s->query(1,0,y);
t2=e->query(1,0,y);
int forred=t2.ss-t1.ss;
forred+=x*(lsz-(t2.ff-t1.ff));
//c3;
if(forblue>=ni&&forred>=ni)return true;
return false;
}
//try doing: only when it starts on a new guy then create new set of pointers
//(e.g. only when updating blue/red then will create new, other colour won't)
void sgnit(int cs, int ce, int cn, vector<int>&v1, vector<int>&v2)
{
if(cs==ce){sg[cn]=v1[cs-1]+v2[cs-1];return;}
int cm=(ce+cs)/2;
sgnit(cs,cm,cn<<1,v1,v2);
sgnit(cm+1,ce,(cn<<1)|1,v1,v2);
sg[cn]=min(sg[cn<<1],sg[(cn<<1)|1]);
}
ll query(int cs, int ce, int cn, int s, int e)
{
if(s<=cs&&e>=ce){return sg[cn];}
ll cm=(cs+ce)/2;
ll ans=LLONG_MAX;
if(s<=cm){ans=query(cs,cm,cn<<1,s,e);}
if(e>cm){ans=min(ans,query(cm+1,ce,(cn<<1)|1,s,e));}
return ans;
}
void init(int N, int Q, vector<int> X, vector<int> Y)
{
n=N;
vector<int>nummys;
for(ll x:X){nummys.pb(x);reds.pb(x);}
for(ll y:Y){nummys.pb(y);blues.pb(y);}
sort(nummys.begin(),nummys.end());
nummys.erase(unique(nummys.begin(),nummys.end()),nummys.end());
revcorr.resize(nummys.size());
for(int i=0;i<nummys.size();i++)
{
corr[nummys[i]]=i;
revcorr[i]=nummys[i];
}
preffys.pb(new Node(0,nummys.size()-1));
for(int a=0;a<N;a++)
{
Node *curr=(preffys.back()->update(corr[blues[a]],0));
curr=curr->update(corr[reds[a]],1);
preffys.pb(curr);
}
sg.resize(4*N+1);
sgnit(1,N,1,X,Y);
}
int max_prize(int L, int R)
{
ll l=L,r=R;
//debu3(preffys.size(),l,r+1);
Node *diyi=preffys[l], *dier=preffys[r+1];
ll hi=query(0,n,1,l+1,r+1)+1,lo=0,mid;
while(hi>lo+1ll)
{
mid=(lo+hi)/2ll;
if(checkers(R-L+1,mid,diyi,dier))
{
lo=mid;
}
else
{
hi=mid;
}
}
return lo;
}
