oj.uz

Submission #996255

# Submission time Handle Problem Language Result Execution time Memory
996255 2024-06-10T09:47:22 Z MilosMilutinovic Train (APIO24_train) C++17
10 / 100
 1000 ms 49932 KB 
#include "train.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int BLOCK = 600;
 
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 856 KB Correct.
2 Correct 3 ms 604 KB Correct.
3 Correct 1 ms 604 KB Correct.
4 Correct 2 ms 604 KB Correct.
5 Correct 1 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 158 ms 20932 KB Correct.
2 Correct 208 ms 38080 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 13 ms 13556 KB Correct.
5 Correct 0 ms 344 KB Correct.
6 Correct 154 ms 19140 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 155 ms 38400 KB Correct.
9 Correct 200 ms 37836 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 20932 KB Correct.
2 Correct 208 ms 38080 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 13 ms 13556 KB Correct.
5 Correct 0 ms 344 KB Correct.
6 Correct 154 ms 19140 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 155 ms 38400 KB Correct.
9 Correct 200 ms 37836 KB Correct.
10 Correct 213 ms 25404 KB Correct.
11 Correct 279 ms 42236 KB Correct.
12 Correct 13 ms 13656 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 377 ms 49600 KB Correct.
15 Correct 240 ms 42204 KB Correct.
16 Execution timed out 1082 ms 49932 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 856 KB Correct.
2 Correct 3 ms 604 KB Correct.
3 Correct 1 ms 604 KB Correct.
4 Correct 2 ms 604 KB Correct.
5 Correct 1 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 1 ms 348 KB Correct.
8 Correct 158 ms 20932 KB Correct.
9 Correct 208 ms 38080 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 13 ms 13556 KB Correct.
12 Correct 0 ms 344 KB Correct.
13 Correct 154 ms 19140 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 155 ms 38400 KB Correct.
16 Correct 200 ms 37836 KB Correct.
17 Correct 213 ms 25404 KB Correct.
18 Correct 279 ms 42236 KB Correct.
19 Correct 13 ms 13656 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Correct 377 ms 49600 KB Correct.
22 Correct 240 ms 42204 KB Correct.
23 Execution timed out 1082 ms 49932 KB Time limit exceeded
24 Halted 0 ms 0 KB -