Submission #1241493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241493		noyancanturk	Overtaking (IOI23_overtaking)	C++20	0 / 100	1 ms	836 KiB

overtaking

#include "overtaking.h"

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

const int lim=1100;

using mint=long long;
using pii=pair<mint,mint>;

mint dp[lim][lim],ansdp[lim][lim];

int n,m,x;

vector<mint>t;
vector<int>w,s;
mint c[lim];
double aa[lim];
int p[lim][lim];
mint reach[lim][lim];

int calc(int i,mint y){
  int l=0,r=n-1,res=-1;
  while(l<=r){
    int mid=l+r>>1;
    if(y==dp[i][p[i][mid]]){
      if(w[p[i][mid]]<x){
        l=mid+1;
        res=mid;
      }else{
        r=mid-1;
      }
    }else if(dp[i][p[i][mid]]<y){
      l=mid+1;
      res=mid;
    }else{
      r=mid-1;
    }
  }
  return res;
}

void init(int L,int N,vector<mint>T,vector<int>W,int X,int M,vector<int> S)
{   
  n=N,m=M,x=X;
  t=T,w=W,s=S;
  for(int i=0;i<n;i++){
    if(w[i]<=x){
      swap(w[i],w.back());
      swap(t[i],t.back());
      w.pop_back();
      t.pop_back();
      i--;
      n--;
    }
  }
  for(int i=0;i<n;i++){
    dp[0][i]=t[i];
  }
  for(int i=0;i+1<m;i++){
    iota(p[i],p[i]+n,0);
    sort(p[i],p[i]+n,[&](int i1,int i2)->bool {
      if(dp[i][i1]^dp[i][i2])return dp[i][i1]<dp[i][i2];
      return w[i1]<w[i2];
    });
    for(int j=0;j<n;j++){
      dp[i+1][j]=dp[i][j]+1ll*w[j]*(s[i+1]-s[i]);
    }
    for(int j=1;j<n;j++){
      dp[i+1][p[i][j]]=max(dp[i+1][p[i][j]],dp[i+1][p[i][j-1]]);
    }
  }
  for(int i=0;i<n;i++){
    ansdp[m-1][i]=dp[m-1][i];
    c[i]=w[i]-x;
    aa[i]=1./c[i];
  }
  for(int i=m-2;0<=i;i--){
    vector<int>inds;
    for(int j=0;j<n;j++){
      if(j+1<n&&dp[i][p[i][j]]==dp[i][p[i][j+1]])continue;
      // cerr<<"calc "<<i<<' '<<p[i][j]<<'\n';
      ansdp[i][p[i][j]]=dp[i][p[i][j]]+1ll*x*(s[m-1]-s[i]);
      if(inds.size()){
        // cerr<<dp[i][p[i][j]]-dp[i][inds.back()]<<'\n';
        mint colloc=s[i]+(dp[i][p[i][j]]-dp[i][inds.back()]+c[inds.back()]-1)/c[inds.back()];
        int willcol=lower_bound(s.begin(),s.end(),colloc)-s.begin();
        if(willcol<m){
          // cerr<<"pull "<<willcol<<' '<<inds.back()<<'\n';
          ansdp[i][p[i][j]]=ansdp[willcol][inds.back()];
        }
      }
      int sz;
      while((sz=inds.size())&&w[sz-1]<w[p[i][j]])inds.pop_back();
      while(1<(sz=inds.size())){
        double a1=-aa[p[i][j]];
        double a2=-aa[inds[sz-1]];
        double a3=-aa[inds[sz-2]];
        double b1=aa[p[i][j]]*dp[i][p[i][j]];
        double b2=aa[inds[sz-1]]*dp[i][inds[sz-1]];
        double b3=aa[inds[sz-2]]*dp[i][inds[sz-2]];
        if((a2-a3)/(b3-b2)<(a1-a2)/(b2-b1)){
          inds.pop_back();
        }else break;
      }
      inds.pb(p[i][j]);
    }
  }
  for(int i=0;i<m;i++){
    reach[p[0][0]][i]=dp[i][p[0][0]];
  }
  for(int i=1;i<n;i++){
    for(int j=0;j<m;j++){
      reach[p[0][i]][j]=max(reach[p[0][i-1]][j],dp[j][p[0][i]]);
    }
  }
  // for(int i=0;i<n;i++){
  //   for(int j=0;j<m;j++){
  //     cerr<<dp[j][i]<<' ';
  //   }cerr<<'\n';
  // }cerr<<'\n';
  // for(int i=0;i<m;i++){
  //   for(int j=0;j<n;j++){
  //     cerr<<ansdp[i][j]<<' ';
  //   }cerr<<'\n';
  // }cerr<<'\n';
  return;
}

mint arrival_time(mint y)
{
  int place=calc(0,y);
  if(place==-1){
    return y+1ll*x*s[m-1];
  }
  int l=0,r=m-1,ans=m;
  while(l<=r){
    int mid=l+r>>1;
    if(y+1ll*x*s[mid]<reach[place][mid]){
      ans=mid;
      r=mid-1;
    }else{
      l=mid+1;
    }
  }
  if(ans==m){
    return y+1ll*x*s[m-1];
  }
  mint globans=reach[place][ans];
  // cerr<<ans<<' '<<globans<<'\n';
  for(int i=n-1;0<=i;i--){
    if(dp[ans][p[ans][i]]==globans){
      // cerr<<"access "<<ans<<' '<<p[ans][i]<<'\n';
      return ansdp[ans][p[ans][i]];
    }
  }
  assert(0);
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35