#1162658 (C++14) No.2242 Cities and Teleporters

• 問題: No.2242 Cities and Teleporters
• ユーザー: norioc
• 提出日時: 2026-05-04 03:41:28
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,938 bytes
• コンパイル時間: 1,392 ms
• コンパイル使用メモリ: 205,664 KB
• 実行使用メモリ: 61,844 KB
• 最終ジャッジ日時: 2026-05-04 03:42:25
• 合計ジャッジ時間: 12,830 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge1_0

ファイルパターン	結果
other	AC * 7 TLE * 2 -- * 17

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:162:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  162 |     for (auto& [h,t,i]: cities) {
      |                ^
main.cpp:178:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  178 |             auto [t, ci] = segt.prod(0, p);
      |                  ^

ソースコード

#include <bits/stdc++.h>
using namespace std;

int ceil_pow2(int n) {
    int x = 0;
    while ((1 << x) < n) x++;
    return x;
}

template <class S>
struct SegTree {
    int _n, size, log;
    vector<S> d;
    function<S(S, S)> op;
    S e;

    SegTree(function<S(S, S)> op, S e, int n) : op(op), e(e) {
        vector<S> v(n, e);
        init(v);
    }

    SegTree(function<S(S, S)> op, S e, const vector<S>& v) : op(op), e(e) {
        init(v);
    }

    void init(const vector<S>& v) {
        _n = (int)v.size();
        log = ceil_pow2(_n);
        size = 1 << log;
        d.assign(2 * size, e);
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) update(i);
    }

    void set(int p, S x) {
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        return d[p + size];
    }

    S prod(int l, int r) {
        S sml = e, smr = e;
        l += size;
        r += size;
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() {
        return d[1];
    }

    template <class F>
    int max_right(int l, F f) {
        if (l == _n) return _n;
        l += size;
        S sm = e;
        bool first = true;
        while (first || (l & -l) != l) {
            first = false;
            while ((l & 1) == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l <<= 1;
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        }
        return _n;
    }

    template <class F>
    int min_left(int r, F f) {
        if (r == 0) return 0;
        r += size;
        S sm = e;
        bool first = true;
        while (first || (r & -r) != r) {
            first = false;
            r--;
            while (r > 1 && (r & 1)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (r << 1) + 1;
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        }
        return 0;
    }

    void update(int k) {
        d[k] = op(d[2 * k], d[2 * k + 1]);
    }
};

struct Doubling {
    int nb;
    vector<vector<int>> d;

    Doubling(const vector<int>& xs, int nb = 60) : nb(nb) {
        int n = xs.size();
        d.assign(nb, vector<int>(n));
        for (int i = 0; i < n; i++) d[0][i] = xs[i];
        for (int k = 0; k < nb - 1; k++) {
            for (int i = 0; i < n; i++) {
                d[k + 1][i] = d[k][d[k][i]];
            }
        }
    }

    int query(long long k, int start) {
        int cur = start;
        for (int i = 0; i < nb; i++) {
            if (k & (1LL << i)) {
                cur = d[i][cur];
            }
        }
        return cur;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> H(N), T(N);
    for (int i = 0; i < N; i++) cin >> H[i];
    for (int i = 0; i < N; i++) cin >> T[i];
    int Q;
    cin >> Q;

    vector<tuple<int,int,int>> cities;
    for (int i = 0; i < N; i++) {
        cities.emplace_back(H[i], T[i], i);
    }
    sort(cities.begin(), cities.end());

    vector<pair<int,int>> init;
    for (auto& [h,t,i]: cities) {
        init.emplace_back(t, i);
    }

    auto op = [](pair<int,int> a, pair<int,int> b) {
        return max(a, b);
    };

    SegTree<pair<int,int>> segt(op, make_pair(0,0), init);

    vector<int> nexts;
    for (int i = 0; i < N; i++) {
        int p = upper_bound(cities.begin(), cities.end(), make_tuple(T[i], INT_MAX, INT_MAX)) - cities.begin();
        if (p == 0) {
            nexts.push_back(i);
        } else {
            auto [t, ci] = segt.prod(0, p);
            if (t > T[i]) nexts.push_back(ci);
            else nexts.push_back(i);
        }
    }

    Doubling d(nexts);

    while (Q--) {
        int A, B;
        cin >> A >> B;
        A--; B--;

        long long k = (long long)1e18;
        int ci = d.query(k, A);

        if (H[B] > T[ci]) {
            cout << -1 << '\n';
            continue;
        }

        long long lo = 0, hi = k, res = k;
        while (lo <= hi) {
            long long m = (lo + hi) / 2;
            int ci2 = d.query(m, A);
            if (T[ci2] >= H[B]) {
                res = min(res, m);
                hi = m - 1;
            } else {
                lo = m + 1;
            }
        }

        cout << res + 1 << '\n';
    }

    return 0;
}