提出 #61608867

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
namespace po167{
template<class T, T(*op)(T, T)>
struct Sparse_table{
    int n;
    int depth;
    std::vector<std::vector<T>> val;
    void init(std::vector<T> &v){
        depth = 1;
        n = v.size();
        while ((1 << depth) <= n) depth++;
        val.resize(depth);
        val[0] = v;
        for (int i = 1; i < depth; i++){
            val[i].resize(n);
            for (int j = 0; j <= n - (1 << i); j++){
                val[i][j] = op(val[i - 1][j], val[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    Sparse_table(std::vector<T> v){
        init(v);
    }
    Sparse_table(){}
    // 0 <= l < r <= n
    // if l == r : assert
    T prod(int l, int r){
        assert(0 <= l && l < r && r <= n);
        int z=31-__builtin_clz(r-l);
        return op(val[z][l], val[z][r - (1 << z)]);
    }
};
}

int op(int a, int b){
    return max(a, b);
}


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

    int N;
    cin >> N;
    vector<int> A(N);
    for (auto &a : A) cin >> a;
    vector<int> C(N);
    {
        int r = 0;
        for (int l = 0; l < N; l++){
            while (r != N && A[l] * 2 > A[r]) r++;
            C[l] = r - l;
        }
    }
    po167::Sparse_table<int, op> S(C);
    int Q;
    cin >> Q;
    while (Q--){
        int l, r;
        cin >> l >> r;
        l--;
        int L = 0, R = (r - l) / 2 + 1;
        while (R - L > 1){
            int M = (L + R) / 2;
            auto tmp = S.prod(l, l + M);
            if (l + M + tmp <= r) L = M;
            else R = M;
        }
        cout << L << "\n";
    }
}

提出情報

ジャッジ結果