oj.uz

Submission #995244

# Submission time Handle Problem Language Result Execution time Memory
995244 2024-06-08T17:32:31 Z huutuan Train (APIO24_train) C++17
5 / 100
 1000 ms 346412 KB 
#include "train.h"

#include <vector>

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=1e6+10, S=500, 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;
   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 24 ms 109804 KB Correct.
2 Correct 24 ms 107608 KB Correct.
3 Correct 20 ms 108124 KB Correct.
4 Correct 21 ms 108784 KB Correct.
5 Correct 17 ms 107096 KB Correct.
6 Correct 18 ms 107096 KB Correct.
7 Correct 17 ms 107296 KB Correct.

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 294920 KB Correct.
2 Correct 443 ms 173488 KB Correct.
3 Correct 17 ms 107100 KB Correct.
4 Correct 24 ms 108052 KB Correct.
5 Correct 17 ms 107100 KB Correct.
6 Execution timed out 1103 ms 346412 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 294920 KB Correct.
2 Correct 443 ms 173488 KB Correct.
3 Correct 17 ms 107100 KB Correct.
4 Correct 24 ms 108052 KB Correct.
5 Correct 17 ms 107100 KB Correct.
6 Execution timed out 1103 ms 346412 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 109804 KB Correct.
2 Correct 24 ms 107608 KB Correct.
3 Correct 20 ms 108124 KB Correct.
4 Correct 21 ms 108784 KB Correct.
5 Correct 17 ms 107096 KB Correct.
6 Correct 18 ms 107096 KB Correct.
7 Correct 17 ms 107296 KB Correct.
8 Correct 971 ms 294920 KB Correct.
9 Correct 443 ms 173488 KB Correct.
10 Correct 17 ms 107100 KB Correct.
11 Correct 24 ms 108052 KB Correct.
12 Correct 17 ms 107100 KB Correct.
13 Execution timed out 1103 ms 346412 KB Time limit exceeded
14 Halted 0 ms 0 KB -