oj.uz

Submission #996414

# Submission time Handle Problem Language Result Execution time Memory
996414 2024-06-10T14:51:41 Z huutuan Train (APIO24_train) C++17
100 / 100
 863 ms 146340 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25176 KB Correct.
2 Correct 7 ms 25180 KB Correct.
3 Correct 7 ms 25024 KB Correct.
4 Correct 6 ms 25180 KB Correct.
5 Correct 6 ms 25024 KB Correct.
6 Correct 6 ms 24924 KB Correct.
7 Correct 6 ms 24924 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 42044 KB Correct.
2 Correct 171 ms 43548 KB Correct.
3 Correct 6 ms 24924 KB Correct.
4 Correct 12 ms 25692 KB Correct.
5 Correct 6 ms 24924 KB Correct.
6 Correct 238 ms 41816 KB Correct.
7 Correct 5 ms 24924 KB Correct.
8 Correct 119 ms 58244 KB Correct.
9 Correct 179 ms 43536 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 42044 KB Correct.
2 Correct 171 ms 43548 KB Correct.
3 Correct 6 ms 24924 KB Correct.
4 Correct 12 ms 25692 KB Correct.
5 Correct 6 ms 24924 KB Correct.
6 Correct 238 ms 41816 KB Correct.
7 Correct 5 ms 24924 KB Correct.
8 Correct 119 ms 58244 KB Correct.
9 Correct 179 ms 43536 KB Correct.
10 Correct 208 ms 46660 KB Correct.
11 Correct 204 ms 48196 KB Correct.
12 Correct 12 ms 25692 KB Correct.
13 Correct 6 ms 24924 KB Correct.
14 Correct 339 ms 146312 KB Correct.
15 Correct 215 ms 48196 KB Correct.
16 Correct 863 ms 46404 KB Correct.
17 Correct 239 ms 82964 KB Correct.

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25176 KB Correct.
2 Correct 7 ms 25180 KB Correct.
3 Correct 7 ms 25024 KB Correct.
4 Correct 6 ms 25180 KB Correct.
5 Correct 6 ms 25024 KB Correct.
6 Correct 6 ms 24924 KB Correct.
7 Correct 6 ms 24924 KB Correct.
8 Correct 164 ms 42044 KB Correct.
9 Correct 171 ms 43548 KB Correct.
10 Correct 6 ms 24924 KB Correct.
11 Correct 12 ms 25692 KB Correct.
12 Correct 6 ms 24924 KB Correct.
13 Correct 238 ms 41816 KB Correct.
14 Correct 5 ms 24924 KB Correct.
15 Correct 119 ms 58244 KB Correct.
16 Correct 179 ms 43536 KB Correct.
17 Correct 208 ms 46660 KB Correct.
18 Correct 204 ms 48196 KB Correct.
19 Correct 12 ms 25692 KB Correct.
20 Correct 6 ms 24924 KB Correct.
21 Correct 339 ms 146312 KB Correct.
22 Correct 215 ms 48196 KB Correct.
23 Correct 863 ms 46404 KB Correct.
24 Correct 239 ms 82964 KB Correct.
25 Correct 210 ms 47944 KB Correct.
26 Correct 218 ms 47940 KB Correct.
27 Correct 232 ms 47992 KB Correct.
28 Correct 242 ms 47944 KB Correct.
29 Correct 229 ms 46400 KB Correct.
30 Correct 276 ms 45988 KB Correct.
31 Correct 263 ms 46148 KB Correct.
32 Correct 272 ms 46144 KB Correct.
33 Correct 394 ms 145992 KB Correct.
34 Correct 380 ms 146244 KB Correct.
35 Correct 374 ms 146340 KB Correct.
36 Correct 275 ms 46232 KB Correct.
37 Correct 214 ms 48200 KB Correct.
38 Correct 508 ms 45968 KB Correct.
39 Correct 257 ms 70976 KB Correct.
40 Correct 219 ms 47900 KB Correct.
41 Correct 199 ms 41284 KB Correct.
42 Correct 199 ms 40360 KB Correct.
43 Correct 243 ms 40012 KB Correct.
44 Correct 224 ms 47936 KB Correct.
45 Correct 229 ms 47936 KB Correct.
46 Correct 230 ms 48156 KB Correct.
47 Correct 188 ms 71708 KB Correct.
48 Correct 206 ms 82468 KB Correct.
49 Correct 184 ms 82500 KB Correct.
50 Correct 199 ms 82368 KB Correct.
51 Correct 202 ms 82244 KB Correct.
52 Correct 176 ms 82240 KB Correct.