Submission #1283658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283658		8pete8	Lottery (JOI25_lottery)	C++20	100 / 100	2028 ms	620704 KiB

lottery

#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
*/

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23