oj.uz

Submission #995824

# Submission time Handle Problem Language Result Execution time Memory
995824 2024-06-09T23:48:43 Z MilosMilutinovic Train (APIO24_train) C++17
10 / 100
 1000 ms 532044 KB 
#include "train.h"
#include <bits/stdc++.h>

using namespace std;

const int BLOCK = 450;

const int N = 100005;
const int MAX = 300 * 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]) {
    ch[x][0] = ++tsz;
    mn[ch[x][0]] = inf;
  }
  if (!ch[x][1]) {
    ch[x][1] = ++tsz;
    mn[ch[x][1]] = inf;
  }
  mn[ch[x][0]] += tag[x];
  mn[ch[x][1]] += tag[x];
  tag[ch[x][0]] += 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) {
    x = ++tsz;
    mn[x] = inf;
  }
  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:220:13: warning: unused variable 'to' [-Wunused-variable]
  220 |         int to = IDX[i][j];
      |             ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 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 344 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 160 ms 20168 KB Correct.
2 Correct 161 ms 33892 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 12 ms 11340 KB Correct.
5 Correct 0 ms 344 KB Correct.
6 Correct 514 ms 21180 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 151 ms 36100 KB Correct.
9 Correct 162 ms 33636 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 20168 KB Correct.
2 Correct 161 ms 33892 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 12 ms 11340 KB Correct.
5 Correct 0 ms 344 KB Correct.
6 Correct 514 ms 21180 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 151 ms 36100 KB Correct.
9 Correct 162 ms 33636 KB Correct.
10 Correct 216 ms 24384 KB Correct.
11 Correct 207 ms 37704 KB Correct.
12 Correct 14 ms 11356 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 421 ms 132676 KB Correct.
15 Correct 218 ms 37700 KB Correct.
16 Execution timed out 1058 ms 532044 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 600 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 344 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 160 ms 20168 KB Correct.
9 Correct 161 ms 33892 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 12 ms 11340 KB Correct.
12 Correct 0 ms 344 KB Correct.
13 Correct 514 ms 21180 KB Correct.
14 Correct 0 ms 344 KB Correct.
15 Correct 151 ms 36100 KB Correct.
16 Correct 162 ms 33636 KB Correct.
17 Correct 216 ms 24384 KB Correct.
18 Correct 207 ms 37704 KB Correct.
19 Correct 14 ms 11356 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Correct 421 ms 132676 KB Correct.
22 Correct 218 ms 37700 KB Correct.
23 Execution timed out 1058 ms 532044 KB Time limit exceeded
24 Halted 0 ms 0 KB -