結果
問題 | No.2242 Cities and Teleporters |
ユーザー |
![]() |
提出日時 | 2023-03-10 22:57:21 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 519 ms / 3,000 ms |
コード長 | 2,017 bytes |
コンパイル時間 | 2,976 ms |
コンパイル使用メモリ | 258,100 KB |
実行使用メモリ | 23,680 KB |
最終ジャッジ日時 | 2024-09-18 05:07:24 |
合計ジャッジ時間 | 14,016 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main() {int n;cin >> n;vector<int> h(n), t(n);for (int i = 0; i < n; i++) {cin >> h.at(i);}for (int i = 0; i < n; i++) {cin >> t.at(i);}int q;cin >> q;vector<int> a(q), b(q);for (int i = 0; i < q; i++) {cin >> a.at(i) >> b.at(i);a.at(i)--;b.at(i)--;}auto h_copy = h;sort(h_copy.begin(), h_copy.end());h_copy.erase(unique(h_copy.begin(), h_copy.end()), h_copy.end());for (int i = 0; i < n; i++) {h.at(i) =upper_bound(h_copy.begin(), h_copy.end(), h.at(i)) - h_copy.begin();t.at(i) =upper_bound(h_copy.begin(), h_copy.end(), t.at(i)) - h_copy.begin();}const int m = h_copy.size();constexpr int l = 20;vector<vector<int>> highest(l, vector<int>(m + 1));for (int i = 0; i <= m; i++) {highest.at(0).at(i) = i;}for (int i = 0; i < n; i++) {highest.at(0).at(h.at(i)) = max(highest.at(0).at(h.at(i)), t.at(i));}for (int i = 0; i < m; i++) {highest.at(0).at(i + 1) =max(highest.at(0).at(i + 1), highest.at(0).at(i));}for (int i = 0; i < l - 1; i++) {for (int j = 0; j <= m; j++) {highest.at(i + 1).at(j) = highest.at(i).at(highest.at(i).at(j));}}for (int i = 0; i < q; i++) {const int ta = t.at(a.at(i)), hb = h.at(b.at(i));assert(ta >= 0 and hb > 0);if (highest.back().at(ta) < hb) {puts("-1");continue;}if (ta >= hb) {puts("1");continue;}int ans = 2, x = ta;while (highest.at(0).at(x) < hb) {int k = 0;while (highest.at(k).at(x) < hb) {k++;}k--;x = highest.at(k).at(x);ans += 1 << k;}cout << ans << "\n";}return 0;}