Submission #996414

#	Time	Username	Problem	Language	Result	Execution time	Memory
996414		huutuan	Train (APIO24_train)	C++17	100 / 100	863 ms	146340 KiB

train

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include "train.h"

#include <vector>

#include <bits/stdc++.h>

using namespace std;
using ll=long long;

const int N=2e5+100, S=4000;
const ll inf=1e18;

struct DS{
   int lazy[N], add[N];
   void update(int x){
      int id=x>>9;
      for (int i=0; i<id; ++i) ++lazy[i];
      for (int i=id<<9; i<=x; ++i) ++add[i];
   }
   int get(int x){
      return lazy[x>>9]+add[x];
   }
} ds;

struct SegmentTree{
   int n;
   vector<ll> val, lazy;
   void init(int _n, ll x=0){
      n=_n;
      lazy.assign(4*n, 0);
      val.assign(4*n, x);
   }
   void apply(int k, ll x){
      val[k]+=x;
      lazy[k]+=x;
   }
   void push(int k){
      if (lazy[k]){
         apply(k<<1, lazy[k]);
         apply(k<<1|1, lazy[k]);
         lazy[k]=0;
      }
   }
   void update(int k, int l, int r, int L, int R, ll x){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         apply(k, x);
         return;
      }
      push(k);
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, x);
      update(k<<1|1, mid+1, r, L, R, x);
      val[k]=min(val[k<<1], val[k<<1|1]);
   }
   ll get(int k, int l, int r, int L, int R){
      if (r<L || R<l) return inf;
      if (L<=l && r<=R) return val[k];
      push(k);
      int mid=(l+r)>>1;
      return min(get(k<<1, l, mid, L, R), get(k<<1|1, mid+1, r, L, R));
   }
};

struct State{
   int u, time;
   State (int _u=0, int _time=0){
      u=_u, time=_time;
   }
   bool operator<(const State &a){
      return tie(u, time)<tie(a.u, a.time);
   }
   bool operator==(const State &a){
      return tie(u, time)==tie(a.u, a.time);
   }
};

vector<State> vs;
vector<int> vt;

int n, m, cost[N], heavy[N];
vector<pair<int, int>> g[N];
vector<int> vv[N], qq[N];
ll f[N], ff[N];
vector<int> add[N];
int id[N];
SegmentTree st[N/S+10];

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) {
   n=N_, m=M;
   for (int i=0; i<n; ++i) cost[i]=T[i];
   vt.push_back(-1);
   vt.push_back(0); vt.push_back(2e9);
   for (int i=0; i<m; ++i) vt.push_back(A[i]), vt.push_back(B[i]);
   sort(vt.begin(), vt.end()); vt.resize(unique(vt.begin(), vt.end())-vt.begin());
   for (int i=0; i<W; ++i){
      L[i]=lower_bound(vt.begin(), vt.end(), L[i])-vt.begin();
      R[i]=upper_bound(vt.begin(), vt.end(), R[i])-vt.begin()-1;
   }
   for (int i=0; i<m; ++i){
      A[i]=lower_bound(vt.begin(), vt.end(), A[i])-vt.begin();
      B[i]=lower_bound(vt.begin(), vt.end(), B[i])-vt.begin();
      vs.emplace_back(X[i], A[i]);
      vs.emplace_back(Y[i], B[i]);
   }
   vs.emplace_back(0, 1);
   vs.emplace_back(n-1, (int)vt.size()-1);
   sort(vs.begin(), vs.end()); vs.resize(unique(vs.begin(), vs.end())-vs.begin());
   for (int i=0; i<m; ++i){
      int i1=lower_bound(vs.begin(), vs.end(), State(X[i], A[i]))-vs.begin();
      int i2=lower_bound(vs.begin(), vs.end(), State(Y[i], B[i]))-vs.begin();
      g[i2].emplace_back(i1, C[i]);
   }
   for (int i=0; i<(int)vs.size(); ++i) vv[vs[i].u].push_back(i), qq[vs[i].time].push_back(i);
   for (int i=0; i<n; ++i) f[i]=inf;
   vector<int> vh;
   for (int i=0; i<n; ++i) if ((int)vv[i].size()>S){
      heavy[i]=1;
      st[vh.size()].init((int)vt.size(), inf);
      id[i]=vh.size();
      vh.push_back(i);
   }
   for (int i=0; i<W; ++i) add[R[i]+1].push_back(L[i]-1);
   for (int i=0; i<N; ++i) f[i]=ff[i]=inf;
   ff[0]=0;
   for (int i=0; i<(int)vt.size(); ++i){
      for (int j:add[i]){
         for (int k=0; k<(int)vh.size(); ++k) st[k].update(1, 1, st[k].n, 1, j, cost[vh[k]]);
         ds.update(j);
      }
      for (int j:qq[i]){
         for (auto &e:g[j]){
            ff[j]=min(ff[j], f[e.first]+e.second);
         }
      }
      for (int j:qq[i]){
         int u=vs[j].u;
         if (heavy[u]){
            st[id[u]].update(1, 1, st[id[u]].n, vs[j].time, vs[j].time, ff[j]-inf);
         }
      }
      for (int j:qq[i]){
         int u=vs[j].u;
         if (heavy[u]){
            f[j]=min(f[j], st[id[u]].get(1, 1, st[id[u]].n, 1, vs[j].time));
         }else{
            for (int k:vv[u]) if (vs[k].time<=vs[j].time){
               f[j]=min(f[j], ff[k]+1ll*ds.get(vs[k].time)*cost[u]);
            }
         }
      }
   }
   ll ans=f[(int)vs.size()-1];
   if (ans==inf) ans=-1;
   return ans;
}

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