oj.uz

Submission #995247

# Submission time Handle Problem Language Result Execution time Memory
995247 2024-06-08T17:36:01 Z huutuan Train (APIO24_train) C++17
0 / 100
 835 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(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;
         ll 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();
   }
   ll ans=f[(int)vs.size()-2];
   if (ans==inf) ans=-1;
   return ans;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 108892 KB Correct.
2 Correct 19 ms 107612 KB Correct.
3 Correct 20 ms 107864 KB Correct.
4 Correct 22 ms 108380 KB Correct.
5 Correct 17 ms 107060 KB Correct.
6 Correct 17 ms 107100 KB Correct.
7 Incorrect 22 ms 107100 KB Wrong Answer.
8 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 243380 KB Correct.
2 Correct 396 ms 159420 KB Correct.
3 Correct 17 ms 107100 KB Correct.
4 Correct 24 ms 107868 KB Correct.
5 Correct 18 ms 107100 KB Correct.
6 Runtime error 823 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 835 ms 243380 KB Correct.
2 Correct 396 ms 159420 KB Correct.
3 Correct 17 ms 107100 KB Correct.
4 Correct 24 ms 107868 KB Correct.
5 Correct 18 ms 107100 KB Correct.
6 Runtime error 823 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 108892 KB Correct.
2 Correct 19 ms 107612 KB Correct.
3 Correct 20 ms 107864 KB Correct.
4 Correct 22 ms 108380 KB Correct.
5 Correct 17 ms 107060 KB Correct.
6 Correct 17 ms 107100 KB Correct.
7 Incorrect 22 ms 107100 KB Wrong Answer.
8 Halted 0 ms 0 KB -