QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#439993 | #8649. Escape Route 2 | nhuang685 | 0 | 27ms | 12400kb | C++20 | 3.6kb | 2024-06-12 22:24:52 | 2024-06-12 22:24:52 |
Judging History
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%