#include"lottery.h" #include<bits/stdc++.h> using namespace std; const int MAXN=2e5+5; long long A[MAXN],B[MAXN]; void init(int n,int q,vector<int> X,vector<int> Y) { for(int i=1;i<=n;i++) A[i]=X[i-1],B[i]=Y[i-1]; } int max_prize(int l,int r) { l++,r++; long long lt=1,rt=2e9,ans=0; for(int i=l;i<=r;i++) rt=min(rt,A[i]+B[i]); while(lt<=rt) { long long mid=(lt+rt)/2,kl=0,kr=0; for(int i=l;i<=r;i++) kl+=mid-min(B[i],mid),kr+=min(A[i],mid); if(kl<=mid*(r-l+1)/2&&mid*(r-l+1)/2<=kr) lt=mid+1,ans=mid; else rt=mid-1; } return ans; }