oj.uz

Submission #995785

# Submission time Handle Problem Language Result Execution time Memory
995785 2024-06-09T23:07:04 Z MilosMilutinovic Train (APIO24_train) C++17
5 / 100
 1000 ms 29128 KB 
#include "train.h"
#include <bits/stdc++.h>

using namespace std;

const int BLOCK = 400;

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;
  });
  const long long inf = (long long) 1e18;
  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);
  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 {
      for (int k = 0; k < j; k++) {
        nd = min(nd, dist[i][k] + Count(my[i][k] + 1, my[i][j] - 1) * 1LL * T[i]);
      }
    }
    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 5 ms 600 KB Correct.
2 Correct 3 ms 600 KB Correct.
3 Correct 3 ms 604 KB Correct.
4 Correct 3 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
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 19104 KB Correct.
2 Correct 172 ms 29128 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 10 ms 8540 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Execution timed out 1043 ms 18112 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 19104 KB Correct.
2 Correct 172 ms 29128 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 10 ms 8540 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Execution timed out 1043 ms 18112 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 600 KB Correct.
2 Correct 3 ms 600 KB Correct.
3 Correct 3 ms 604 KB Correct.
4 Correct 3 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 406 ms 19104 KB Correct.
9 Correct 172 ms 29128 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 10 ms 8540 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Execution timed out 1043 ms 18112 KB Time limit exceeded
14 Halted 0 ms 0 KB -