oj.uz

Submission #996407

# Submission time Handle Problem Language Result Execution time Memory
996407 2024-06-10T14:45:57 Z huutuan Train (APIO24_train) C++17
10 / 100
 1000 ms 146720 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 5 ms 25176 KB Correct.
2 Correct 5 ms 25180 KB Correct.
3 Correct 5 ms 25036 KB Correct.
4 Correct 5 ms 25180 KB Correct.
5 Correct 6 ms 24924 KB Correct.
6 Correct 4 ms 24920 KB Correct.
7 Correct 4 ms 24920 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 42044 KB Correct.
2 Correct 156 ms 43588 KB Correct.
3 Correct 4 ms 24920 KB Correct.
4 Correct 12 ms 25688 KB Correct.
5 Correct 3 ms 24924 KB Correct.
6 Correct 241 ms 41876 KB Correct.
7 Correct 4 ms 24920 KB Correct.
8 Correct 126 ms 58212 KB Correct.
9 Correct 177 ms 43540 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 42044 KB Correct.
2 Correct 156 ms 43588 KB Correct.
3 Correct 4 ms 24920 KB Correct.
4 Correct 12 ms 25688 KB Correct.
5 Correct 3 ms 24924 KB Correct.
6 Correct 241 ms 41876 KB Correct.
7 Correct 4 ms 24920 KB Correct.
8 Correct 126 ms 58212 KB Correct.
9 Correct 177 ms 43540 KB Correct.
10 Correct 210 ms 46656 KB Correct.
11 Correct 211 ms 48412 KB Correct.
12 Correct 11 ms 25692 KB Correct.
13 Correct 4 ms 24924 KB Correct.
14 Correct 397 ms 146720 KB Correct.
15 Correct 222 ms 48252 KB Correct.
16 Execution timed out 1057 ms 46228 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25176 KB Correct.
2 Correct 5 ms 25180 KB Correct.
3 Correct 5 ms 25036 KB Correct.
4 Correct 5 ms 25180 KB Correct.
5 Correct 6 ms 24924 KB Correct.
6 Correct 4 ms 24920 KB Correct.
7 Correct 4 ms 24920 KB Correct.
8 Correct 161 ms 42044 KB Correct.
9 Correct 156 ms 43588 KB Correct.
10 Correct 4 ms 24920 KB Correct.
11 Correct 12 ms 25688 KB Correct.
12 Correct 3 ms 24924 KB Correct.
13 Correct 241 ms 41876 KB Correct.
14 Correct 4 ms 24920 KB Correct.
15 Correct 126 ms 58212 KB Correct.
16 Correct 177 ms 43540 KB Correct.
17 Correct 210 ms 46656 KB Correct.
18 Correct 211 ms 48412 KB Correct.
19 Correct 11 ms 25692 KB Correct.
20 Correct 4 ms 24924 KB Correct.
21 Correct 397 ms 146720 KB Correct.
22 Correct 222 ms 48252 KB Correct.
23 Execution timed out 1057 ms 46228 KB Time limit exceeded
24 Halted 0 ms 0 KB -