結果
問題 | No.2242 Cities and Teleporters |
ユーザー | jiangly |
提出日時 | 2023-03-11 00:45:21 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 470 ms / 3,000 ms |
コード長 | 1,814 bytes |
コンパイル時間 | 2,280 ms |
コンパイル使用メモリ | 210,820 KB |
実行使用メモリ | 20,392 KB |
最終ジャッジ日時 | 2023-10-18 09:23:39 |
合計ジャッジ時間 | 11,579 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 341 ms
20,392 KB |
testcase_06 | AC | 265 ms
20,392 KB |
testcase_07 | AC | 363 ms
20,392 KB |
testcase_08 | AC | 470 ms
20,392 KB |
testcase_09 | AC | 460 ms
20,392 KB |
testcase_10 | AC | 198 ms
20,392 KB |
testcase_11 | AC | 243 ms
20,392 KB |
testcase_12 | AC | 241 ms
20,392 KB |
testcase_13 | AC | 268 ms
20,392 KB |
testcase_14 | AC | 313 ms
20,392 KB |
testcase_15 | AC | 263 ms
20,392 KB |
testcase_16 | AC | 277 ms
20,392 KB |
testcase_17 | AC | 329 ms
20,392 KB |
testcase_18 | AC | 273 ms
20,152 KB |
testcase_19 | AC | 334 ms
20,072 KB |
testcase_20 | AC | 253 ms
19,672 KB |
testcase_21 | AC | 242 ms
19,752 KB |
testcase_22 | AC | 327 ms
19,672 KB |
testcase_23 | AC | 323 ms
20,392 KB |
testcase_24 | AC | 338 ms
20,392 KB |
testcase_25 | AC | 324 ms
20,392 KB |
ソースコード
#include <bits/stdc++.h> using i64 = long long; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N; std::cin >> N; std::vector<int> H(N), T(N); for (int i = 0; i < N; i++) { std::cin >> H[i]; } for (int i = 0; i < N; i++) { std::cin >> T[i]; } const int logN = std::__lg(N); std::vector f(logN + 1, std::vector(N, -1)); std::vector<int> order(N); std::iota(order.begin(), order.end(), 0); std::sort(order.begin(), order.end(), [&](int i, int j) { return H[i] < H[j]; }); std::vector<int> pre(N); pre[0] = order[0]; for (int i = 1; i < N; i++) { pre[i] = T[order[i]] > T[pre[i - 1]] ? order[i] : pre[i - 1]; } for (int i = 0; i < N; i++) { int j = std::partition_point(order.begin(), order.end(), [&](int x) { return H[x] <= T[i]; }) - order.begin(); if (j > 0) { f[0][i] = pre[j - 1]; } if (f[0][i] == -1 || (T[i] > T[f[0][i]])) { f[0][i] = i; } } for (int j = 0; j < logN; j++) { for (int i = 0; i < N; i++) { f[j + 1][i] = f[j][f[j][i]]; } } int Q; std::cin >> Q; while (Q--) { int A, B; std::cin >> A >> B; A--, B--; int ans = 0; for (int i = logN; i >= 0; i--) { if (T[f[i][A]] < H[B]) { ans += 1 << i; A = f[i][A]; } } if (T[A] < H[B]) { A = f[0][A]; ans += 1; } if (T[A] < H[B]) { ans = -1; } else { ans += 1; } std::cout << ans << "\n"; } return 0; }