結果
問題 | No.2242 Cities and Teleporters |
ユーザー |
![]() |
提出日時 | 2023-03-10 22:25:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 355 ms / 3,000 ms |
コード長 | 1,976 bytes |
コンパイル時間 | 2,245 ms |
コンパイル使用メモリ | 222,692 KB |
最終ジャッジ日時 | 2025-02-11 08:37:52 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include<bits/stdc++.h>namespace {#pragma GCC diagnostic ignored "-Wunused-function"#include<atcoder/all>#pragma GCC diagnostic warning "-Wunused-function"using namespace std;using namespace atcoder;#define rep(i,n) for(int i = 0; i < (int)(n); i++)#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)#define all(x) begin(x), end(x)#define rall(x) rbegin(x), rend(x)template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;} int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;VI h(n), t(n);rep(i, n) cin >> h[i];rep(i, n) cin >> t[i];vector<int> ord(n);iota(ord.begin(), ord.end(), 0);sort(ord.begin(), ord.end(), [&](int i, int j) {return h[i] < h[j];});VI rank(n);rep(i, n) rank[ord[i]] = i;VI to(n, -1);VI to_d[18];rep(u, n) {auto it = upper_bound(all(ord), t[u], [&](int x, int i) {return x < h[i];});if (it != ord.begin()) to[u] = *prev(it);}to_d[0].resize(n);{int now = ord[0];rep(i, n) {int u = ord[i];if (rank[u] > rank[now]) now = u;if (to[u] != -1 && rank[to[u]] > rank[now]) now = to[u];to_d[0][u] = now;}}rep(i, 17) {to_d[i+1].resize(n, -1);rep(v, n) to_d[i+1][v] = to_d[i][to_d[i][v]];}int q;cin >> q;while(q--) {int a, b;cin >> a >> b;a--, b--;if (to[a] == -1) {cout << -1 << '\n';continue;}int ans = 1;a = to[a];rrep(k, 18) {int v = to_d[k][a];if (rank[v] < rank[b]) ans += 1 << k, a = v;}if (rank[a] < rank[b]) ans++, a = to_d[0][a];if (rank[a] < rank[b]) ans = -1;cout << ans << '\n';}}