ACPC2014 Day2 I Hard Beans

問題文

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2014Day2&pid=I

解法

WaveletMatrixで殴ると通ります．
具体的には，区間の何番目の値が D との大小関係の境界になっているか quantile で二分探索するだけです．

ソースコード

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

// wavelet matrix が長すぎる

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    for(int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    wavelet_matrix<int> wm(a);
    int Q;
    cin >> Q;
    while(Q--) {
        int l, r, D;
        cin >> l >> r >> D;
        int lb = 0, ub = r - l;
        while(ub - lb > 1) {
            int m = (ub + lb) / 2;
            if(wm.quantile(l, r + 1, m) >= D) {
                lb = m;
            } else {
                ub = m;
            }
        }
        cout << min(abs(wm.quantile(l, r + 1, lb) - D), abs(wm.quantile(l, r + 1, ub) - D)) << endl;
    }
}

感想

想定解はなんだろう？流石にWaveletMatrixで殴れって問題じゃないはずだけども．