oj.uz

Submission #995811

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

using namespace std;

const int BLOCK = 0;

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;
  auto Count = [&](int from, int to) {
    int total = 0;
    for (int i = 0; i < w; i++) {
      if (from <= L[i] && R[i] <= to) {
        total += 1;
      }
    }
    return total;
  };
  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];
  });
  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 = (int) (lower_bound(xs.begin(), xs.end(), my[i][k]) - xs.begin());
        int to = (int) (lower_bound(xs.begin(), xs.end(), my[i][j]) - xs.begin());
        nd = min(nd, dist[i][k] + (fenw.get(to - 1) - 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;
      }
      int idx = (int) (lower_bound(xs.begin(), xs.end(), t) - xs.begin());
      nd = min(nd, Query(root[i], 0, k - 1, 0, idx));
      Modify(root[i], 0, k - 1, idx, 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]);
    }
  }
  long long res = inf;
  for (int i = 0; i < sz[n - 1]; i++) {
    res = min(res, dist[n - 1][i] + Count(my[n - 1][i] + 1, 1000) * 1LL * T[n - 1]);
  }
  if (res == inf) {
    return -1;
  } else {
    return res;
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2648 KB Correct.
2 Correct 3 ms 5472 KB Correct.
3 Correct 2 ms 4956 KB Correct.
4 Correct 2 ms 4956 KB Correct.
5 Correct 0 ms 2396 KB Correct.
6 Correct 1 ms 2396 KB Correct.
7 Correct 1 ms 2392 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 54436 KB Correct.
2 Correct 217 ms 69216 KB Correct.
3 Correct 1 ms 2396 KB Correct.
4 Correct 12 ms 11080 KB Correct.
5 Correct 1 ms 2396 KB Correct.
6 Correct 215 ms 48856 KB Correct.
7 Correct 0 ms 2396 KB Correct.
8 Correct 142 ms 32964 KB Correct.
9 Correct 220 ms 72908 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 54436 KB Correct.
2 Correct 217 ms 69216 KB Correct.
3 Correct 1 ms 2396 KB Correct.
4 Correct 12 ms 11080 KB Correct.
5 Correct 1 ms 2396 KB Correct.
6 Correct 215 ms 48856 KB Correct.
7 Correct 0 ms 2396 KB Correct.
8 Correct 142 ms 32964 KB Correct.
9 Correct 220 ms 72908 KB Correct.
10 Execution timed out 1041 ms 490304 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2648 KB Correct.
2 Correct 3 ms 5472 KB Correct.
3 Correct 2 ms 4956 KB Correct.
4 Correct 2 ms 4956 KB Correct.
5 Correct 0 ms 2396 KB Correct.
6 Correct 1 ms 2396 KB Correct.
7 Correct 1 ms 2392 KB Correct.
8 Correct 182 ms 54436 KB Correct.
9 Correct 217 ms 69216 KB Correct.
10 Correct 1 ms 2396 KB Correct.
11 Correct 12 ms 11080 KB Correct.
12 Correct 1 ms 2396 KB Correct.
13 Correct 215 ms 48856 KB Correct.
14 Correct 0 ms 2396 KB Correct.
15 Correct 142 ms 32964 KB Correct.
16 Correct 220 ms 72908 KB Correct.
17 Execution timed out 1041 ms 490304 KB Time limit exceeded
18 Halted 0 ms 0 KB -