結果

問題 No.2242 Cities and Teleporters
ユーザー Jeroen Op de BeekJeroen Op de Beek
提出日時 2023-03-10 22:23:20
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 330 ms / 3,000 ms
コード長 3,292 bytes
コンパイル時間 2,543 ms
コンパイル使用メモリ 218,336 KB
実行使用メモリ 30,232 KB
最終ジャッジ日時 2024-09-18 04:32:59
合計ジャッジ時間 10,575 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
struct LCA {
    vi par,d,jmp,in,out;
    vector<basic_string<int>> adj;
    int root;
    LCA(int n,int root=0) : par(n,root),d(n),jmp(n,root),in(n),out(n),adj(n),root(root) {}
    void add(int i) {
        int p = par[i];
        d[i]=1+d[p];
        if(d[p] - d[jmp[p]] == d[jmp[p]] - d[jmp[jmp[p]]]) jmp[i] = jmp[jmp[p]];
        else jmp[i] = p;
    }
    int jump(int a, int k) {
        int D = max(0,d[a]-k);
        while(d[a]>D) {
            if(d[jmp[a]]>=D) a = jmp[a];
            else a = par[a];
        }
        return a;
    }
    template<typename F> pi find(int a, F f) {
        int steps=d[a];
        while(!f(a)) {
            if(!f(jmp[a])) a = jmp[a];
            else a = par[a];
        }
        steps-=d[a];
        return {a,steps};
    }
    int lca(int a, int b) {
        if(d[a]<d[b]) swap(a,b);
        a = jump(a,d[a]-d[b]);
        while(a!=b) {
            if(jmp[a]!=jmp[b]) a=jmp[a],b=jmp[b];
            else a=par[a],b=par[b];
        }
        return a;
    }
    void addE(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int cnt=0;
    void dfs(int at) {
        in[at]=cnt++;
        for(int to: adj[at]) if(to!=par[at])  {
            par[to]=at;
            add(to);
            dfs(to);
        }
        out[at]=cnt;
    }
    void init() {
        dfs(root);
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    vi h(n),t(n);
    for(auto& i : h) cin >> i;
    for(auto& i : t) cin >> i;
    vi ord(n);
    iota(all(ord),0);
    sort(all(ord),[&](int i,int j) {return h[i]<h[j];});
    vi iord(n);
    for(int i=0;i<n;++i) iord[ord[i]]=i;
    vi hh=h;
    sort(all(hh));
    vi best(n,0);
    for(int i=0;i<n;++i) {
        int to = upper_bound(all(hh),t[i])-hh.begin() - 1;
        best[iord[i]]=to; // last one you can reach, -1 if not reachable
    }
    LCA lca(n+1,n);
    for(int i=0;i<n;++i) {
        if(i) best[i]=max(best[i],best[i-1]);
        if(best[i]>i) lca.addE(i,best[i]);
        else lca.addE(i,n);
    }
    lca.init();

    // i --> <=t[i] some prefix of all the stuff.
    // only first one is different. so go to prefix then start jumping?
    int q; cin >> q;
    while(q--) {
        int a,b; cin >> a >> b;
        --a,--b;
        a = upper_bound(all(hh),t[a])-hh.begin()-1;
        if(a==-1) {
            cout << "-1\n";
        } else {
            auto [who,steps] = lca.find(a,[&](int i) {return i==n or hh[i]>=h[b];});
            if(who==n) {
                cout << "-1\n";
            } else cout << steps+1 << '\n';
        }
    }

}
0