oj.uz

Submission #996222

# Submission time Handle Problem Language Result Execution time Memory
996222 2024-06-10T08:55:50 Z MilosMilutinovic Train (APIO24_train) C++17
10 / 100
 1000 ms 51812 KB 
#include "train.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int BLOCK = 450;
 
const int N = 100005;
const int MAX = 200 * N;
 
const long long inf = (long long) 1e18;
 
int root[N], tsz, ch[MAX][2];
long long mn[MAX], tag[MAX];
 
void push(int x) {
  if (!x || !tag[x]) {
    return;
  }
  if (ch[x][0]) {
    mn[ch[x][0]] += tag[x];
    tag[ch[x][0]] += tag[x];
  }
  if (!ch[x][1]) {
    mn[ch[x][1]] += tag[x];
    tag[ch[x][1]] += tag[x];
  }
  tag[x] = 0;
}
 
void pull(int x) {
  mn[x] = inf;
  if (ch[x][0]) {
    mn[x] = min(mn[x], mn[ch[x][0]]);
  }
  if (ch[x][1]) {
    mn[x] = min(mn[x], mn[ch[x][1]]);
  }
}
 
void AddRange(int& x, int l, int r, int ll, int rr, int v) {
  if (ll > rr) {
    return;
  }
  if (!x) {
    return;
  }
  if (ll <= l && r <= rr) {
    tag[x] += v;
    mn[x] += v;
    push(x);
    return;
  }
  push(x);
  int mid = (l + r) >> 1;
  if (rr <= mid) {
    AddRange(ch[x][0], l, mid, ll, rr, v);
  } else if (ll > mid) {
    AddRange(ch[x][1], mid + 1, r, ll, rr, v);
  } else {
    AddRange(ch[x][0], l, mid, ll, rr, v);
    AddRange(ch[x][1], mid + 1, r, ll, rr, v);
  }
  pull(x);
}
 
void Modify(int& x, int l, int r, int i, long long v) {
  if (!x) {
    x = ++tsz;
    mn[x] = inf;
  }
  if (l == r) {
    mn[x] = min(mn[x], v);
    return;
  }
  push(x);
  int mid = (l + r) >> 1;
  if (i <= mid) {
    Modify(ch[x][0], l, mid, i, v);
  } else {
    Modify(ch[x][1], mid + 1, r, i, v);
  }
  pull(x);
}
 
long long Query(int v, int l, int r, int ll, int rr) {
  if (!v) {
    return inf;
  }
  if (ll <= l && r <= rr) {
    return mn[v];
  }
  push(v);
  int mid = (l + r) >> 1;
  long long ret = inf;
  if (rr <= mid) {
    ret = Query(ch[v][0], l, mid, ll, rr);
  } else if (ll > mid) {
    ret = Query(ch[v][1], mid + 1, r, ll, rr);
  } else {
    ret = min(Query(ch[v][0], l, mid, ll, rr), Query(ch[v][1], mid + 1, r, ll, rr));
  }
  pull(v);
  return ret;
}
 
template <typename T>
class fenwick {
 public:
  vector<T> fenw;
  int n;
 
  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
 
  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }
 
  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};
 
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) {
  vector<vector<int>> my(n);
  for (int i = 0; i < m; i++) {
    my[X[i]].push_back(A[i]);
    my[Y[i]].push_back(B[i]);
  }
  my[0].push_back(0);
  vector<int> sz(n);
  for (int i = 0; i < n; i++) {
    sort(my[i].begin(), my[i].end());
    if (!my[i].empty()) {
      my[i].erase(unique(my[i].begin(), my[i].end()), my[i].end());
    }
    sz[i] = (int) my[i].size();
  }
  vector<pair<int, int>> vec;
  for (int i = 0; i < n; i++) {
    for (int j : my[i]) {
      vec.emplace_back(i, j);
    }
  }
  sort(vec.begin(), vec.end(), [&](pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
  });
  vector<vector<long long>> dist(n);
  for (int i = 0; i < n; i++) {
    dist[i].resize(sz[i], inf);
  }
  dist[0][0] = 0;
  vector<int> xs;
  for (int i = 0; i < w; i++) {
    xs.push_back(L[i]);
    xs.push_back(R[i]);
  }
  for (int i = 0; i < n; i++) {
    for (int j : my[i]) {
      xs.push_back(j);
    }
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  vector<vector<vector<int>>> g(n);
  for (int i = 0; i < n; i++) {
    g[i].resize(sz[i]);
  }
  for (int i = 0; i < m; i++) {
    int idx = (int) (lower_bound(my[X[i]].begin(), my[X[i]].end(), A[i]) - my[X[i]].begin());
    g[X[i]][idx].push_back(i);
  }
  vector<array<int, 2>> segs;
  for (int i = 0; i < w; i++) {
    segs.push_back({L[i], R[i]});
  }
  sort(segs.begin(), segs.end(), [&](array<int, 2> a, array<int, 2> b) {
    return a[1] < b[1];
  });
  vector<vector<int>> IDX(n);
  for (int i = 0; i < n; i++) {
    IDX[i].resize(sz[i]);
    for (int j = 0; j < sz[i]; j++) {
      IDX[i][j] = (int) (lower_bound(xs.begin(), xs.end(), my[i][j]) - xs.begin());
    }
  }
  int ptr = 0;
  int k = (int) xs.size();
  fenwick<int> fenw(k);
  vector<int> nxt(n);
  vector<vector<int>> active(n);
  for (int qq = 0; qq < (int) vec.size(); qq++) {
    int i = vec[qq].first;
    int t = vec[qq].second;
    int j = (int) (lower_bound(my[i].begin(), my[i].end(), t) - my[i].begin());
    while (ptr < (int) segs.size() && segs[ptr][1] < t) { 
      fenw.modify((int) (lower_bound(xs.begin(), xs.end(), segs[ptr][0]) - xs.begin()), +1);
      ptr += 1;
    }
    long long nd = dist[i][j];
    if (sz[i] < BLOCK) {
      auto Value = [&](int k) {
        int from = IDX[i][k];
        int to = IDX[i][j];
        return dist[i][k] + (ptr - fenw.get(from)) * 1LL * T[i];
      };
      while (active[i].size() >= 2 && Value(active[i].rbegin()[1]) <= Value(active[i].rbegin()[0])) {
        active[i].pop_back();
      }
      for (int j : active[i]) {
        nd = min(nd, Value(j));
      }
      active[i].push_back(j);
    } else {
      while (nxt[i] < (int) segs.size() && segs[nxt[i]][1] < t) {
        int idx = (int) (lower_bound(xs.begin(), xs.end(), segs[nxt[i]][0]) - xs.begin());
        AddRange(root[i], 0, k - 1, 0, idx - 1, T[i]);
        nxt[i] += 1;
      }
      nd = min(nd, Query(root[i], 0, k - 1, 0, IDX[i][j]));
      Modify(root[i], 0, k - 1, IDX[i][j], dist[i][j]);
    }
    for (auto& p : g[i][j]) {
      int to = Y[p];
      int time = B[p];
      int idx = (int) (lower_bound(my[to].begin(), my[to].end(), time) - my[to].begin());
      dist[to][idx] = min(dist[to][idx], nd + C[p]);
    }
  }
  ptr = 0;
  sort(segs.begin(), segs.end(), [&](array<int, 2> a, array<int, 2> b) {
    return a[0] > b[0];
  });
  long long res = inf;
  for (int i = sz[n - 1] - 1; i >= 0; i--) {
    while (ptr < (int) segs.size() && segs[ptr][0] > my[n - 1][i]) {
      ptr++;
    }
    res = min(res, dist[n - 1][i] + ptr * 1LL * T[n - 1]);
  }
  if (res == inf) {
    return -1;
  } else {
    return res;
  }
}

Compilation message

train.cpp: In lambda function:
train.cpp:216:13: warning: unused variable 'to' [-Wunused-variable]
  216 |         int to = IDX[i][j];
      |             ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct.
2 Correct 1 ms 608 KB Correct.
3 Correct 1 ms 640 KB Correct.
4 Correct 1 ms 604 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 1 ms 348 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 21100 KB Correct.
2 Correct 207 ms 38236 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 13 ms 13668 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 165 ms 21132 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 157 ms 38596 KB Correct.
9 Correct 205 ms 37832 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 21100 KB Correct.
2 Correct 207 ms 38236 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 13 ms 13668 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 165 ms 21132 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 157 ms 38596 KB Correct.
9 Correct 205 ms 37832 KB Correct.
10 Correct 261 ms 25404 KB Correct.
11 Correct 246 ms 42312 KB Correct.
12 Correct 13 ms 13644 KB Correct.
13 Correct 1 ms 344 KB Correct.
14 Correct 374 ms 49604 KB Correct.
15 Correct 258 ms 42052 KB Correct.
16 Execution timed out 1091 ms 51812 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct.
2 Correct 1 ms 608 KB Correct.
3 Correct 1 ms 640 KB Correct.
4 Correct 1 ms 604 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 1 ms 348 KB Correct.
8 Correct 155 ms 21100 KB Correct.
9 Correct 207 ms 38236 KB Correct.
10 Correct 0 ms 348 KB Correct.
11 Correct 13 ms 13668 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 165 ms 21132 KB Correct.
14 Correct 0 ms 344 KB Correct.
15 Correct 157 ms 38596 KB Correct.
16 Correct 205 ms 37832 KB Correct.
17 Correct 261 ms 25404 KB Correct.
18 Correct 246 ms 42312 KB Correct.
19 Correct 13 ms 13644 KB Correct.
20 Correct 1 ms 344 KB Correct.
21 Correct 374 ms 49604 KB Correct.
22 Correct 258 ms 42052 KB Correct.
23 Execution timed out 1091 ms 51812 KB Time limit exceeded
24 Halted 0 ms 0 KB -