oj.uz

Submission #996207

# Submission time Handle Problem Language Result Execution time Memory
996207 2024-06-10T08:51:10 Z MilosMilutinovic Train (APIO24_train) C++17
10 / 100
 1000 ms 51572 KB 
#include "train.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int BLOCK = 500;
 
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();
      }
      if (!active[i].empty()) {
        nd = min(nd, Value(active[i].back()));
      }
      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 2 ms 604 KB Correct.
3 Correct 1 ms 604 KB Correct.
4 Correct 1 ms 600 KB Correct.
5 Correct 1 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 141 ms 21080 KB Correct.
2 Correct 189 ms 38340 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Correct 13 ms 13640 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 137 ms 21244 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 156 ms 38500 KB Correct.
9 Correct 192 ms 37836 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 21080 KB Correct.
2 Correct 189 ms 38340 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Correct 13 ms 13640 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 137 ms 21244 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 156 ms 38500 KB Correct.
9 Correct 192 ms 37836 KB Correct.
10 Correct 192 ms 25228 KB Correct.
11 Correct 267 ms 42316 KB Correct.
12 Correct 12 ms 13660 KB Correct.
13 Correct 1 ms 348 KB Correct.
14 Correct 383 ms 49628 KB Correct.
15 Correct 238 ms 42304 KB Correct.
16 Execution timed out 1065 ms 51572 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 2 ms 604 KB Correct.
3 Correct 1 ms 604 KB Correct.
4 Correct 1 ms 600 KB Correct.
5 Correct 1 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 141 ms 21080 KB Correct.
9 Correct 189 ms 38340 KB Correct.
10 Correct 1 ms 348 KB Correct.
11 Correct 13 ms 13640 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 137 ms 21244 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 156 ms 38500 KB Correct.
16 Correct 192 ms 37836 KB Correct.
17 Correct 192 ms 25228 KB Correct.
18 Correct 267 ms 42316 KB Correct.
19 Correct 12 ms 13660 KB Correct.
20 Correct 1 ms 348 KB Correct.
21 Correct 383 ms 49628 KB Correct.
22 Correct 238 ms 42304 KB Correct.
23 Execution timed out 1065 ms 51572 KB Time limit exceeded
24 Halted 0 ms 0 KB -