oj.uz

Submission #995245

# Submission time Handle Problem Language Result Execution time Memory
995245 2024-06-08T17:33:06 Z huutuan Train (APIO24_train) C++17
5 / 100
 865 ms 1048576 KB 
#include "train.h"

#include <vector>

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=1e6+10, S=1000, inf=1e18;

struct Node{
   int val, lazy;
   Node (int _val=0){
      val=_val, lazy=0;
   }
   Node operator+(const Node &a){
      return Node(min(val, a.val));
   }
};

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

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

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

int n, m, cost[N], heavy[N];
vector<pair<int, int>> g[N];
vector<int> vv[N];
int f[N], vis[N];
vector<pair<int, pair<int, int>>> query[N];
vector<int> add[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void process_heavy(int u){
   st.init((int)vt.size(), inf);
   for (int i=1; i<(int)vv[u].size(); i+=2) st.update(1, 1, st.n, vs[vv[u][i]].time, vs[vv[u][i]].time, f[vv[u][i]]-inf);
   for (int i=0, j=0; i<(int)vt.size(); ++i){
      for (int k:add[i]) st.update(1, 1, st.n, 1, k, cost[u]);
      while (j<(int)vv[u].size() && (vs[vv[u][j]].time<i)) j+=2;
      if (j>=(int)vv[u].size()) break;
      if (vs[vv[u][j]].time==i){
         f[vv[u][j]]=min(f[vv[u][j]], st.get(1, 1, st.n, 1, i).val);
         pq.emplace(f[vv[u][j]], vv[u][j]);
      }
   }
}

long long solve(int32_t N_, int32_t M, int32_t W, std::vector<int32_t> T, std::vector<int32_t> X, std::vector<int32_t> Y,
                std::vector<int32_t> A, std::vector<int32_t> B, std::vector<int32_t> C, std::vector<int32_t> L,
                std::vector<int32_t> R) {
   n=N_, m=M;
   for (int i=0; i<n; ++i) cost[i]=T[i];
   for (int i=0; i<W; ++i){
      vt.push_back(L[i]);
      vt.push_back(R[i]);
   }
   vt.push_back(-1);
   vt.push_back(0); vt.push_back(1e9);
   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());
   st.init((int)vt.size());
   for (int i=0; i<W; ++i){
      L[i]=lower_bound(vt.begin(), vt.end(), L[i])-vt.begin();
      R[i]=lower_bound(vt.begin(), vt.end(), R[i])-vt.begin();
   }
   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], 0);
      vs.emplace_back(X[i], A[i], 1);
      vs.emplace_back(Y[i], B[i], 0);
      vs.emplace_back(Y[i], B[i], 1);
   }
   vs.emplace_back(0, 1, 0);
   vs.emplace_back(0, 1, 1);
   vs.emplace_back(n-1, (int)vt.size()-1, 0);
   vs.emplace_back(n-1, (int)vt.size()-1, 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], 0))-vs.begin();
      int i2=lower_bound(vs.begin(), vs.end(), State(Y[i], B[i], 1))-vs.begin();
      g[i1].emplace_back(i2, C[i]);
   }
   for (int i=0; i<(int)vs.size(); ++i) vv[vs[i].u].push_back(i);
   for (int i=0; i<n; ++i) heavy[i]=(int)vv[i].size()>=S, f[i]=inf;
   heavy[0]=1;
   for (int i=0; i<n; ++i) if (!heavy[i]){
      for (int j=1; j<(int)vv[i].size(); j+=2) for (int k=j-1; k<(int)vv[i].size(); k+=2){
         query[vs[vv[i][k]].time].push_back({vs[vv[i][j]].time, {vv[i][j], (int)g[vv[i][j]].size()}});
         g[vv[i][j]].emplace_back(vv[i][k], 0);
      }
   }
   for (int i=0; i<W; ++i) add[R[i]+1].push_back(L[i]-1);
   for (int i=0; i<(int)vt.size(); ++i){
      for (int j:add[i]) st.update(1, 1, st.n, 1, j, 1);
      for (auto &j:query[i]) g[j.second.first][j.second.second].second=st.get(1, 1, st.n, j.first, j.first).val*cost[vs[j.second.first].u];
   }
   for (int i=0; i<N; ++i) f[i]=inf;
   // for (int i=0; i<N; ++i) for (auto &e:g[i]){
   //    int j=e.first, w=e.second;
   //    cout << vs[i].u << ' ' << vt[vs[i].time] << ' ' << vs[i].type << ' ' << vs[j].u << ' ' << vt[vs[j].time] << ' ' << vs[j].type << ' ' << w << '\n';
   // }
   f[1]=0;
   process_heavy(0);
   vector<int> qq;
   while (pq.size()){
      while (pq.size()){
         int u=pq.top().second, d=pq.top().first;
         pq.pop();
         if (f[u]!=d) continue;
         for (auto &e:g[u]){
            int v=e.first, w=e.second;
            if (f[v]>d+w){
               f[v]=d+w;
               if (heavy[vs[v].u]){
                  if (!vis[vs[v].u]){
                     vis[vs[v].u]=1;
                     qq.push_back(vs[v].u);
                  }
               }else pq.emplace(f[v], v);
            }
         }
      }
      for (int u:qq) process_heavy(u);
      qq.clear();
   }
   int ans=f[(int)vs.size()-2];
   if (ans==inf) ans=-1;
   return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 109880 KB Correct.
2 Correct 21 ms 107608 KB Correct.
3 Correct 20 ms 108052 KB Correct.
4 Correct 21 ms 108636 KB Correct.
5 Correct 17 ms 107100 KB Correct.
6 Correct 17 ms 107352 KB Correct.
7 Correct 17 ms 107100 KB Correct.

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 865 ms 294284 KB Correct.
2 Correct 409 ms 174232 KB Correct.
3 Correct 16 ms 107100 KB Correct.
4 Correct 24 ms 108020 KB Correct.
5 Correct 16 ms 107100 KB Correct.
6 Runtime error 743 ms 1048576 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 865 ms 294284 KB Correct.
2 Correct 409 ms 174232 KB Correct.
3 Correct 16 ms 107100 KB Correct.
4 Correct 24 ms 108020 KB Correct.
5 Correct 16 ms 107100 KB Correct.
6 Runtime error 743 ms 1048576 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 109880 KB Correct.
2 Correct 21 ms 107608 KB Correct.
3 Correct 20 ms 108052 KB Correct.
4 Correct 21 ms 108636 KB Correct.
5 Correct 17 ms 107100 KB Correct.
6 Correct 17 ms 107352 KB Correct.
7 Correct 17 ms 107100 KB Correct.
8 Correct 865 ms 294284 KB Correct.
9 Correct 409 ms 174232 KB Correct.
10 Correct 16 ms 107100 KB Correct.
11 Correct 24 ms 108020 KB Correct.
12 Correct 16 ms 107100 KB Correct.
13 Runtime error 743 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -