#1161657 (C++23) No.1332 Range Nearest Query

• 問題: No.1332 Range Nearest Query
• ユーザー: FplusFplusF
• 提出日時: 2026-04-25 19:34:20
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,213 bytes
• コンパイル時間: 2,602 ms
• コンパイル使用メモリ: 347,448 KB
• 実行使用メモリ: 45,944 KB
• 最終ジャッジ日時: 2026-04-25 19:36:01
• 合計ジャッジ時間: 51,465 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_0

ファイルパターン	結果
other	AC * 46 TLE * 2

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll,ll>;
using ld=long double;
constexpr ll INF=(1ll<<60);
#define rep(i,n) for (ll i=0;i<(ll)(n);i++)
#define replr(i,l,r) for (ll i=(ll)(l);i<(ll)(r);i++)
#define all(v) v.begin(),v.end()
#define len(v) ((ll)v.size())
template<class T> inline bool chmin(T &a,T b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

template<class T> struct wavelet_matrix{
    int h=0,n;
    vector<vector<int>> sum;  //[b]=bからb-1への向きの総和
    vector<int> center;
    
    wavelet_matrix(vector<T> a):n(len(a)){
        
        T mx=0;
        rep(i,n) chmax(mx,a[i]);
        while((1ll<<h)<=mx) h++;
        
        sum.resize(h);
        center.assign(h,0);
        
        for(int b=h-1;0<=b;b--){
            
            vector<int> dir(n);
            vector<int> l,r;
            
            rep(i,n){
                dir[i]=(a[i]>>b)&1;
                if(dir[i]==0) l.push_back(a[i]);
                else r.push_back(a[i]);
            }
            
            
            sum[b].assign(n+1,0);
            
            rep(i,n) sum[b][i+1]=sum[b][i]+dir[i];
            
            center[b]=n-sum[b][n];
            
            
            int l_sz=len(l),r_sz=len(r);
            
            rep(i,l_sz) a[i]=l[i];
            rep(i,r_sz) a[l_sz+i]=r[i];
            
        }
    }
    
    
    tuple<int,int,int,int> get_subtree_range(int b,int l,int r){
        int lc1=sum[b][l],lc0=l-lc1;
        int rc1=sum[b][r],rc0=r-rc1;
        int c=center[b];
        return {lc0,rc0,c+lc1,c+rc1};
    }
    
    T kth_smallest_rec(int b,int l,int r,int k){
        
        
        if(b==0) return 0;
        
        auto [l0,r0,l1,r1]=get_subtree_range(b-1,l,r);
        int sz_0=r0-l0;
        
        if(k<sz_0){
            return kth_smallest_rec(b-1,l0,r0,k);
        }else{
            return (1ll<<(b-1))+kth_smallest_rec(b-1,l1,r1,k-sz_0);
        }
    }
    
    T kth_smallest(int l,int r,int k){
        return kth_smallest_rec(h,l,r,k);
    }
    
    
};

template<class T> T binary_search(auto f,T ok,T ng){
    while(1<abs(ok-ng)){
        T mid=midpoint(ok,ng);
        if(f(mid)) ok=mid;
        else ng=mid;
    }
    return ok;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n;
    cin >> n;
    
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    
    wavelet_matrix w(a);
    
    ll q;
    cin >> q;
    
    while(q--){
        ll l,r,x;
        cin >> l >> r >> x;
        l--;
        
        auto get=[&](ll k){
            return w.kth_smallest(l,r,k);
        };
        
        auto f=[&](ll k){
            return get(k)<=x;
        };
        
        ll ans=INF;
        
        if(!f(0)){
            ans=abs(get(0)-x);
        }else{
            ll k=binary_search<ll>(f,0,r-l);
            chmin(ans,abs(get(k)-x));
            if(k+1<r-l) chmin(ans,abs(get(k+1)-x));
        }
        
        cout << ans << '\n';
    }
    
}