Submission #1171233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171233		kim	Train (APIO24_train)	C++20	5 / 100	434 ms	75160 KiB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second
#define eb emplace_back
#define sz(x) (int)x.size()
#define add(x,y) ((x+y)%md)
#define Add(x,y) (x=add(x,y))
#define mul(x,y) ((x*y)%md)
#define Mul(x,y) (x=mul(x,y))
template<class T> T chmn(T &x,T y){ return x=min(x,y); }
template<class T> T chmx(T &x,T y){ return x=max(x,y); }
const int inf=1e9;
const ll linf=1e18;
const ll md=1e9+7;

struct segment{
  struct node{
    node *l,*r;
    int x;
    node(int x=0):x(x),l(l),r(r){}
  };
  using pnode=node*;
  vector<pnode> rt;
  int l0,r0;
  void init(int n,int l,int r){
    rt.resize(n+5);
    l0=l,r0=r;
    build(rt[0],l0,r0);
  }
  void build(pnode &t,int il,int ir){
    t=new node();
    if(il>=ir) return;
    int mid=il+ir>>1;
    build(t->l,il,mid), build(t->r,mid+1,ir);
  }
  void upd(int t0,int t1,int id,int x){ upd(rt[t0],rt[t1],l0,r0,id,x); }
  void upd(pnode t0,pnode &t1,int il,int ir,int id,int x){
    t1=new node(*t0);
    t1->x+=x;
    if(il>=ir) return;
    int mid=il+ir>>1;
    if(id<=mid) upd(t0->l,t1->l,il,mid,id,x);
    else upd(t0->r,t1->r,mid+1,ir,id,x);
  }
  int qr(int t,int l,int r){ return qr(rt[t],l0,r0,l,r); }
  int qr(pnode t,int il,int ir,int l,int r){
    if(il>r||ir<l) return 0;
    if(l<=il&&ir<=r) return t->x;
    int mid=il+ir>>1;
    return qr(t->l,il,mid,l,r)+qr(t->r,mid+1,ir,l,r);
  }
}t;

vector<pair<ll,pii>> dp[100005];
int R[100005];
vector<int> Lcmp;

long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
                std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> L_,
                std::vector<int> R_) {
  vector<int> v(W);
  iota(v.begin(),v.end(),0);
  sort(v.begin(),v.end(),[&](const int &l,const int &r){ return R_[l]<R_[r]; });
  for(int i=0;i<W;++i) Lcmp.eb(L_[i]);
  sort(Lcmp.begin(),Lcmp.end());
  Lcmp.erase(unique(Lcmp.begin(),Lcmp.end()),Lcmp.end());
  t.init(W+5,0,sz(Lcmp));
  for(int i=0;i<W;++i){
    R[i]=R_[v[i]];
    t.upd(i,i+1,lower_bound(Lcmp.begin(),Lcmp.end(),L_[v[i]])-Lcmp.begin(),1);
  }

  dp[0].eb(0,pii(-1,0));
  v.resize(M);
  iota(v.begin(),v.end(),0);
  sort(v.begin(),v.end(),[&](const int &l,const int &r){ return B[l]==B[r] ? A[l]<A[r] : B[l]<B[r]; });
  for(auto &i:v){
    int ver = lower_bound(R,R+W,A[i])-R;
    int l=-1,r=sz(dp[X[i]])-1;
    while(l<r){
      int mid=l+r+1>>1;
      if(dp[X[i]][mid].s.s>ver) r=mid-1;
      else l=mid;
    }
    if(l!=-1){
      int id = upper_bound(Lcmp.begin(),Lcmp.end(),dp[X[i]][l].s.f)-Lcmp.begin();
      ll cost = C[i] + dp[X[i]][l].f + (ll)T[X[i]]*t.qr(ver,id,sz(Lcmp));

      ver = lower_bound(R,R+W,B[i])-R;
      while(!dp[Y[i]].empty() && dp[Y[i]].back().s.s>=ver){
        ll c0 = dp[Y[i]].back().f - (ll)T[Y[i]]*t.qr(dp[Y[i]].back().s.s,0,upper_bound(Lcmp.begin(),Lcmp.end(),dp[Y[i]].back().s.f)-Lcmp.begin()-1);
        ll c1 = cost - (ll)T[Y[i]]*t.qr(dp[Y[i]].back().s.s,0,upper_bound(Lcmp.begin(),Lcmp.end(),B[i])-Lcmp.begin()-1);
        if(c0<c1) break;
        dp[Y[i]].pop_back();
      }
      if(dp[Y[i]].empty()) dp[Y[i]].eb(cost,pii(B[i],ver));
      else{
        l=max(ver,dp[Y[i]].back().s.s+1), r=W+1;
        while(l<r){
          int mid=l+r>>1;
          ll c0 = dp[Y[i]].back().f - (ll)T[Y[i]]*t.qr(mid,0,upper_bound(Lcmp.begin(),Lcmp.end(),dp[Y[i]].back().s.f)-Lcmp.begin()-1);
          ll c1 = cost - (ll)T[Y[i]]*t.qr(mid,0,upper_bound(Lcmp.begin(),Lcmp.end(),B[i])-Lcmp.begin()-1);
          if(c0>c1) r=mid;
          else l=mid+1;
        }
        if(l!=W+1) dp[Y[i]].eb(cost,pii(B[i],l));
      }
    }
  }
  if(dp[N-1].empty()) return -1;
  ll res=1e18;
  for(auto &[c,b]:dp[N-1]){
    int id=upper_bound(Lcmp.begin(),Lcmp.end(),b.f)-Lcmp.begin();
    chmn(res,c+(ll)T[N-1]*t.qr(W,id,sz(Lcmp)));
  }
  return res;
}

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60