#include"lottery.h" #include<bits/stdc++.h> using namespace std; const int MAXN=2e5+5; int A[MAXN],pos[MAXN],va[MAXN],vb[MAXN],V[MAXN],sp[MAXN][20],lg,N; int getlog(long long n) { return 63-__builtin_clzll(n); } bool comp(int a,int b) { return A[a]<A[b]; } struct node { vector<long long> pref; vector<int> idx; void build(int l,int r) { for(int i=l;i<=r;i++) idx.push_back(pos[i]); sort(idx.begin(),idx.end()); long long sum=0; for(auto v:idx) pref.push_back(sum+=A[v]); } pair<long long,int> get(int l,int r) { r=upper_bound(idx.begin(),idx.end(),r)-idx.begin()-1; l=lower_bound(idx.begin(),idx.end(),l)-idx.begin()-1; if(r<0) return {0,0}; if(l<0) return {pref[r],r+1}; return {pref[r]-pref[l],r-l}; } }; node fa[MAXN],fb[MAXN]; int rmq(int l,int r) { int g=getlog(r-l+1); return min(sp[l][g],sp[r-(1<<g)+1][g]); } void init(int n,int q,vector<int> X,vector<int> Y) { lg=getlog(n),N=n; for(int i=1;i<=n;i++) A[i]=X[i-1],pos[i]=i; sort(pos+1,pos+n+1,comp); for(int i=1;i<=n;i++) va[i]=A[pos[i]],fa[i].build(i-(i&-i)+1,i); for(int i=1;i<=n;i++) A[i]=Y[i-1],pos[i]=i; sort(pos+1,pos+n+1,comp); for(int i=1;i<=n;i++) vb[i]=A[pos[i]],fb[i].build(i-(i&-i)+1,i); for(int i=1;i<=n;i++) sp[i][0]=X[i-1]+Y[i-1]; for(int j=1;(1<<j)<=n;j++) for(int i=1;i<=n-(1<<j)+1;i++) sp[i][j]=min(sp[i][j-1],sp[i+(1<<(j-1))][j-1]); } int max_prize(int l,int r) { l++,r++; int pa=0,pb=0,lena=-(r-l+1)/2,lenb=-(r-l+1)/2; long long suma=0,sumb=0; for(int i=lg;i+1;i--) { if(pa+(1<<i)<=N) { pair<long long,int> res=fa[pa+(1<<i)].get(l,r); if(suma+res.first>=1LL*va[pa+(1<<i)]*(lena+res.second)) pa+=(1<<i),suma+=res.first,lena+=res.second; } if(pb+(1<<i)<=N) { pair<long long,int> res=fb[pb+(1<<i)].get(l,r); if(sumb+res.first>=1LL*vb[pb+(1<<i)]*(lenb+res.second)) pb+=(1<<i),sumb+=res.first,lenb+=res.second; } } return min((long long)rmq(l,r),min(suma/lena,sumb/lenb)); }