oj.uz

Submission #995252

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

#include <vector>

#include <bits/stdc++.h>

using namespace std;
using ll=long long;

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

struct Node{
   ll val, lazy;
   Node (ll _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, ll val=0){
      n=_n;
      t.assign(4*n+1, Node(val));
      t[0]=Node(inf);
   }
   void apply(int k, ll 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, ll 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, ll>> g[N];
vector<int> vv[N];
ll f[N];
int vis[N];
vector<pair<int, pair<int, int>>> query[N];
vector<int> add[N];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, 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(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];
   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(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());
   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;
         ll d=pq.top().first;
         pq.pop();
         if (f[u]!=d) continue;
         for (auto &e:g[u]){
            int v=e.first;
            ll 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();
   }
   ll 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 23 ms 109020 KB Correct.
2 Correct 18 ms 107612 KB Correct.
3 Correct 21 ms 107760 KB Correct.
4 Correct 23 ms 108380 KB Correct.
5 Correct 18 ms 107096 KB Correct.
6 Correct 23 ms 107100 KB Correct.
7 Correct 19 ms 107100 KB Correct.

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 906 ms 242904 KB Correct.
2 Correct 411 ms 159176 KB Correct.
3 Correct 23 ms 107052 KB Correct.
4 Correct 31 ms 107864 KB Correct.
5 Correct 18 ms 107100 KB Correct.
6 Runtime error 833 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 906 ms 242904 KB Correct.
2 Correct 411 ms 159176 KB Correct.
3 Correct 23 ms 107052 KB Correct.
4 Correct 31 ms 107864 KB Correct.
5 Correct 18 ms 107100 KB Correct.
6 Runtime error 833 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 23 ms 109020 KB Correct.
2 Correct 18 ms 107612 KB Correct.
3 Correct 21 ms 107760 KB Correct.
4 Correct 23 ms 108380 KB Correct.
5 Correct 18 ms 107096 KB Correct.
6 Correct 23 ms 107100 KB Correct.
7 Correct 19 ms 107100 KB Correct.
8 Correct 906 ms 242904 KB Correct.
9 Correct 411 ms 159176 KB Correct.
10 Correct 23 ms 107052 KB Correct.
11 Correct 31 ms 107864 KB Correct.
12 Correct 18 ms 107100 KB Correct.
13 Runtime error 833 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -