oj.uz

Submission #996215

# Submission time Handle Problem Language Result Execution time Memory
996215 2024-06-10T08:53:01 Z MilosMilutinovic Train (APIO24_train) C++17
40 / 100
 266 ms 43892 KB 
#include "train.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int BLOCK = 100000;
 
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 3 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 174 ms 20928 KB Correct.
2 Correct 186 ms 38080 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 12 ms 13660 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 131 ms 19068 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 132 ms 34904 KB Correct.
9 Correct 181 ms 37732 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 20928 KB Correct.
2 Correct 186 ms 38080 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 12 ms 13660 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 131 ms 19068 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 132 ms 34904 KB Correct.
9 Correct 181 ms 37732 KB Correct.
10 Correct 200 ms 25620 KB Correct.
11 Correct 254 ms 42724 KB Correct.
12 Correct 12 ms 13656 KB Correct.
13 Correct 1 ms 344 KB Correct.
14 Correct 163 ms 22724 KB Correct.
15 Correct 230 ms 42228 KB Correct.
16 Correct 171 ms 22860 KB Correct.
17 Correct 182 ms 43892 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct.
2 Correct 3 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 174 ms 20928 KB Correct.
9 Correct 186 ms 38080 KB Correct.
10 Correct 0 ms 348 KB Correct.
11 Correct 12 ms 13660 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 131 ms 19068 KB Correct.
14 Correct 0 ms 344 KB Correct.
15 Correct 132 ms 34904 KB Correct.
16 Correct 181 ms 37732 KB Correct.
17 Correct 200 ms 25620 KB Correct.
18 Correct 254 ms 42724 KB Correct.
19 Correct 12 ms 13656 KB Correct.
20 Correct 1 ms 344 KB Correct.
21 Correct 163 ms 22724 KB Correct.
22 Correct 230 ms 42228 KB Correct.
23 Correct 171 ms 22860 KB Correct.
24 Correct 182 ms 43892 KB Correct.
25 Correct 265 ms 42308 KB Correct.
26 Correct 239 ms 42048 KB Correct.
27 Correct 251 ms 42228 KB Correct.
28 Correct 266 ms 42228 KB Correct.
29 Correct 200 ms 25408 KB Correct.
30 Incorrect 188 ms 23104 KB Wrong Answer.
31 Halted 0 ms 0 KB -