QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#439993#8649. Escape Route 2nhuang6850 27ms12400kbC++203.6kb2024-06-12 22:24:522024-06-12 22:24:52

Judging History

你现在查看的是最新测评结果

  • [2024-06-12 22:24:52]
  • 评测
  • 测评结果:0
  • 用时:27ms
  • 内存:12400kb
  • [2024-06-12 22:24:52]
  • 提交

answer

/**
 * @file qoj8649-2.cpp
 * @author n685
 * @brief
 * @date 2024-06-11
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif

const int64_t LLINF = static_cast<int64_t>(4e18);
const int LG = 18;

auto solve(int n, int64_t t, std::vector<int> m,
           std::vector<std::vector<std::pair<int64_t, int64_t>>> f, int q,
           std::vector<std::pair<int, int>> qq) -> std::vector<int64_t> {
  for (int i = 0; i < n - 1; ++i) {
    std::sort(f[i].begin(), f[i].end());
    int64_t mi = LLINF;
    for (int j = m[i] - 1; j >= 0; --j) {
      mi = std::min(mi, f[i][j].second);
      f[i][j].second = mi;
    }
  }
  std::vector lift(LG, std::vector<std::vector<int64_t>>(n - 1));
  for (int i = 0; i < n - 1; ++i) {
    lift[0][i].resize(m[i] + 1);
    for (int j = 0; j < m[i]; ++j) {
      lift[0][i][j] = f[i][j].second;
    }
    lift[0][i][m[i]] = t + f[i][0].second;
  }
  for (int i = 1; i < LG; ++i) {
    for (int j = 0; j < n - 1 && j + (1 << i) < n; ++j) {
      lift[i][j].resize(m[j] + 1);
      for (int k = 0; k <= m[j]; ++k) {
        int64_t time = lift[i - 1][j][k];
        int mid = j + (1 << i >> 1);
        int ind = static_cast<int>(
            std::lower_bound(f[mid].begin(), f[mid].end(),
                             std::pair{time % t, static_cast<int64_t>(0)}) -
            f[mid].begin());
        lift[i][j][k] = t * (time / t) + lift[i - 1][mid][ind];
      }
    }
  }
  auto query = [&](int l, int r, int ind) -> int64_t {
    int64_t dist = r - l;
    int64_t st = f[l][ind].first;
    int64_t time = f[l][ind].first;
    for (int i = LG - 1; i >= 0; --i) {
      if (((1 << i) & dist) == 0) {
        continue;
      }
      if (st != time) {
        ind = static_cast<int>(
            std::lower_bound(f[l].begin(), f[l].end(),
                             std::pair{time % t, static_cast<int64_t>(0)}) -
            f[l].begin());
      }
      time = t * (time / t) + lift[i][l][ind];
      int nxt = l + (1 << i);
      l = nxt;
    }
    return time - st;
  };
  std::vector<int64_t> ans(q, LLINF);
  std::set<std::pair<int, int>> s;
  for (int j = 0; j < q; ++j) {
    auto [l, r] = qq[j];
    if (m[l] > m[r - 1] || s.contains({l, r})) {
      continue;
    }
    s.emplace(l, r);
    for (int i = 0; i < m[l]; ++i) {
      ans[j] = std::min(ans[j], query(l, r, i));
    }
  }
  return ans;
}

auto main() -> int {
#ifndef LOCAL
  std::cin.tie(nullptr)->sync_with_stdio(false);
#endif

  int n;
  int64_t t;
  std::cin >> n >> t;

  std::vector<int> m(n);
  std::vector<std::vector<std::pair<int64_t, int64_t>>> f(n - 1);
  for (int i = 0; i < n - 1; ++i) {
    std::cin >> m[i];
    f[i].resize(m[i]);
    for (auto &[a, b] : f[i]) {
      std::cin >> a >> b;
    }
  }
  int q;
  std::cin >> q;
  std::vector<std::pair<int, int>> qq(q);
  for (int i = 0; i < q; ++i) {
    std::cin >> qq[i].first >> qq[i].second;
    --qq[i].first;
    --qq[i].second;
  }
  std::vector<int64_t> a1 = solve(n, t, m, f, q, qq);
  m.pop_back();
  std::reverse(m.begin(), m.end());
  std::reverse(f.begin(), f.end());
  for (int i = 0; i < n - 1; ++i) {
    for (auto &[a, b] : f[i]) {
      a = (t - 1) - a;
      b = (t - 1) - b;
      std::swap(a, b);
    }
  }
  m.push_back(0);
  for (auto &[l, r] : qq) {
    l = (n - 1) - l;
    r = (n - 1) - r;
    std::swap(l, r);
  }
  std::vector<int64_t> a2 = solve(n, t, m, f, q, qq);
  for (int i = 0; i < q; ++i) {
    std::cout << std::min(a1[i], a2[i]) << '\n';
  }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 27ms
memory: 12400kb

input:

2 1000000000
1
359893566 955414858
300000
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 ...

output:

595521292
4000000000000000000
4000000000000000000
4000000000000000000
4000000000000000000
4000000000000000000
4000000000000000000
4000000000000000000
4000000000000000000
4000000000000000000
4000000000000000000
4000000000000000000
4000000000000000000
4000000000000000000
4000000000000000000
4000000000...

result:

wrong answer 2nd lines differ - expected: '595521292', found: '4000000000000000000'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Time Limit Exceeded

Test #39:

score: 0
Time Limit Exceeded

input:

301 1000000000
300
863578477 865166395
261293731 262628986
290161866 292035987
31029640 32135494
288138979 289416854
321254857 322352244
163393949 166291828
897880953 899050317
840019366 842900569
100947276 102350870
520716771 522094941
820182602 822928836
766708508 769688128
727827782 728874133
740...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

0%