oj.uz

Submission #995821

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

using namespace std;

const int BLOCK = 270;

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];
  });
  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] + (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;
      }
      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:170:8: warning: variable 'Count' set but not used [-Wunused-but-set-variable]
  170 |   auto Count = [&](int from, int to) {
      |        ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 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 196 ms 20228 KB Correct.
2 Correct 170 ms 33728 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 12 ms 11356 KB Correct.
5 Correct 1 ms 348 KB Correct.
6 Correct 321 ms 37596 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 152 ms 36288 KB Correct.
9 Correct 192 ms 33484 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 20228 KB Correct.
2 Correct 170 ms 33728 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 12 ms 11356 KB Correct.
5 Correct 1 ms 348 KB Correct.
6 Correct 321 ms 37596 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 152 ms 36288 KB Correct.
9 Correct 192 ms 33484 KB Correct.
10 Correct 247 ms 24124 KB Correct.
11 Correct 213 ms 37880 KB Correct.
12 Correct 18 ms 11352 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 431 ms 146392 KB Correct.
15 Correct 216 ms 37860 KB Correct.
16 Execution timed out 1092 ms 582028 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 1 ms 348 KB Correct.
8 Correct 196 ms 20228 KB Correct.
9 Correct 170 ms 33728 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 12 ms 11356 KB Correct.
12 Correct 1 ms 348 KB Correct.
13 Correct 321 ms 37596 KB Correct.
14 Correct 0 ms 344 KB Correct.
15 Correct 152 ms 36288 KB Correct.
16 Correct 192 ms 33484 KB Correct.
17 Correct 247 ms 24124 KB Correct.
18 Correct 213 ms 37880 KB Correct.
19 Correct 18 ms 11352 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Correct 431 ms 146392 KB Correct.
22 Correct 216 ms 37860 KB Correct.
23 Execution timed out 1092 ms 582028 KB Time limit exceeded
24 Halted 0 ms 0 KB -