oj.uz

Submission #996170

# Submission time Handle Problem Language Result Execution time Memory
996170 2024-06-10T08:26:11 Z MilosMilutinovic Train (APIO24_train) C++17
10 / 100
 1000 ms 51020 KB 
#include "train.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int BLOCK = 333;
 
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);
  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) {
      for (int k = 0; k < j; k++) {
        int from = IDX[i][k];
        int to = IDX[i][j];
        nd = min(nd, dist[i][k] + (ptr - fenw.get(from)) * 1LL * T[i]);
      }
    } 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 function 'long long int solve(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:215:13: warning: unused variable 'to' [-Wunused-variable]
  215 |         int to = IDX[i][j];
      |             ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Correct.
2 Correct 2 ms 604 KB Correct.
3 Correct 1 ms 604 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 0 ms 348 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 20336 KB Correct.
2 Correct 170 ms 33728 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 11 ms 11356 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 472 ms 21720 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 163 ms 36192 KB Correct.
9 Correct 169 ms 33524 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 20336 KB Correct.
2 Correct 170 ms 33728 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 11 ms 11356 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 472 ms 21720 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 163 ms 36192 KB Correct.
9 Correct 169 ms 33524 KB Correct.
10 Correct 211 ms 24208 KB Correct.
11 Correct 219 ms 37956 KB Correct.
12 Correct 12 ms 11352 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 391 ms 49516 KB Correct.
15 Correct 211 ms 37696 KB Correct.
16 Execution timed out 1044 ms 51020 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Correct.
2 Correct 2 ms 604 KB Correct.
3 Correct 1 ms 604 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 0 ms 348 KB Correct.
8 Correct 162 ms 20336 KB Correct.
9 Correct 170 ms 33728 KB Correct.
10 Correct 0 ms 348 KB Correct.
11 Correct 11 ms 11356 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 472 ms 21720 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 163 ms 36192 KB Correct.
16 Correct 169 ms 33524 KB Correct.
17 Correct 211 ms 24208 KB Correct.
18 Correct 219 ms 37956 KB Correct.
19 Correct 12 ms 11352 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Correct 391 ms 49516 KB Correct.
22 Correct 211 ms 37696 KB Correct.
23 Execution timed out 1044 ms 51020 KB Time limit exceeded
24 Halted 0 ms 0 KB -