Submission #1170673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170673		kim	Train (APIO24_train)	C++20	10 / 100	272 ms	74816 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,int>> 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,-1);
  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 l=-1,r=sz(dp[X[i]])-1;
    while(l<r){
      int mid=l+r+1>>1;
      if(dp[X[i]][mid].s>A[i]) r=mid-1;
      else l=mid;
    }
    if(l!=-1){
      l=0;
      int ver=lower_bound(R,R+W,A[i])-R;

      while(l<r){
        int mid=l+r>>1;
        int id=upper_bound(Lcmp.begin(),Lcmp.end(),dp[X[i]][mid].s)-Lcmp.begin();
        int id2=upper_bound(Lcmp.begin(),Lcmp.end(),dp[X[i]][mid+1].s)-Lcmp.begin();
        if(dp[X[i]][mid].f+(ll)T[X[i]]*t.qr(ver,id,sz(Lcmp)) < dp[X[i]][mid+1].f+(ll)T[X[i]]*t.qr(ver,id2,sz(Lcmp))) r=mid;
        else l=mid+1;
      }
      int id=upper_bound(Lcmp.begin(),Lcmp.end(),dp[X[i]][l].s)-Lcmp.begin();
      ll cost = C[i] + dp[X[i]][l].f+(ll)T[X[i]]*t.qr(ver,id,sz(Lcmp));

      // ll cost=1e18;
      // for(int j=l;j<=r;++j){
      //   int id=upper_bound(Lcmp.begin(),Lcmp.end(),dp[X[i]][j].s)-Lcmp.begin();
      //   chmn(cost, dp[X[i]][j].f+(ll)T[X[i]]*t.qr(ver,id,sz(Lcmp)));
      // }
      // cost+=C[i];
      while(!dp[Y[i]].empty() && dp[Y[i]].back().f>=cost) dp[Y[i]].pop_back();
      dp[Y[i]].eb(cost,B[i]);
    }
  }
  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)-Lcmp.begin();
    chmn(res,c+(ll)T[N-1]*t.qr(W,id,sz(Lcmp)));
  }
  return res;
}

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