結果

問題 No.1332 Range Nearest Query
ユーザー outlineoutline
提出日時 2021-01-08 22:26:32
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 543 ms / 2,500 ms
コード長 6,931 bytes
コンパイル時間 1,742 ms
コンパイル使用メモリ 148,592 KB
実行使用メモリ 12,160 KB
最終ジャッジ日時 2024-04-28 03:47:37
合計ジャッジ時間 22,527 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 505 ms
10,880 KB
testcase_04 AC 511 ms
10,880 KB
testcase_05 AC 511 ms
11,008 KB
testcase_06 AC 338 ms
12,032 KB
testcase_07 AC 333 ms
12,032 KB
testcase_08 AC 334 ms
12,032 KB
testcase_09 AC 337 ms
11,904 KB
testcase_10 AC 338 ms
12,032 KB
testcase_11 AC 344 ms
12,032 KB
testcase_12 AC 343 ms
12,160 KB
testcase_13 AC 346 ms
11,904 KB
testcase_14 AC 345 ms
12,032 KB
testcase_15 AC 337 ms
12,160 KB
testcase_16 AC 523 ms
12,160 KB
testcase_17 AC 534 ms
12,032 KB
testcase_18 AC 524 ms
12,032 KB
testcase_19 AC 521 ms
12,032 KB
testcase_20 AC 528 ms
12,032 KB
testcase_21 AC 543 ms
12,032 KB
testcase_22 AC 543 ms
12,032 KB
testcase_23 AC 541 ms
11,904 KB
testcase_24 AC 525 ms
11,904 KB
testcase_25 AC 521 ms
11,904 KB
testcase_26 AC 177 ms
11,904 KB
testcase_27 AC 268 ms
12,160 KB
testcase_28 AC 174 ms
5,376 KB
testcase_29 AC 177 ms
5,376 KB
testcase_30 AC 183 ms
5,376 KB
testcase_31 AC 166 ms
5,376 KB
testcase_32 AC 184 ms
5,376 KB
testcase_33 AC 182 ms
5,376 KB
testcase_34 AC 172 ms
5,376 KB
testcase_35 AC 171 ms
5,376 KB
testcase_36 AC 166 ms
5,376 KB
testcase_37 AC 180 ms
5,376 KB
testcase_38 AC 414 ms
7,808 KB
testcase_39 AC 273 ms
5,376 KB
testcase_40 AC 525 ms
11,648 KB
testcase_41 AC 324 ms
5,376 KB
testcase_42 AC 404 ms
7,552 KB
testcase_43 AC 357 ms
5,888 KB
testcase_44 AC 468 ms
9,728 KB
testcase_45 AC 451 ms
9,216 KB
testcase_46 AC 393 ms
6,912 KB
testcase_47 AC 435 ms
8,320 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <array>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
using namespace std;

using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

struct SuccinctIndexableDictionary {
    size_t length, blocks;
    vector<unsigned> bit, sum;

    SuccinctIndexableDictionary() = default;

    SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) {
        bit.assign(blocks, 0U);
        sum.assign(blocks, 0U);
    }

    void set(int k){
        bit[k >> 5] |= 1U << (k & 31);
    }

    void build(){
        sum[0] = 0U;
        for(int i = 1; i < blocks; ++i){
            sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);
        }
    }

    bool operator[](int k){
        return (bool((bit[k >> 5] >> (k & 31)) & 1));
    }

    int rank(int k){
        return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));
    }

    // f : bit flag
    int rank(bool f, int k){
        return (f ? rank(k) : k - rank(k));
    }
};

template<typename T, int MAXLOG>
struct WaveletMatrix {
    size_t length;
    SuccinctIndexableDictionary matrix[MAXLOG];
    int mid[MAXLOG];

    WaveletMatrix() = default;

    WaveletMatrix(vector<T> v) : length(v.size()) {
        vector<T> zero(length), one(length);
        for(int level = MAXLOG - 1; level >= 0; --level){
            matrix[level] = SuccinctIndexableDictionary(length + 1);
            int left = 0, right = 0;
            for(int i = 0; i < length; ++i){
                if(((v[i] >> level) & 1)){
                    matrix[level].set(i);
                    one[right++] = v[i];
                }
                else{
                    zero[left++] = v[i];
                }
            }
            mid[level] = left;
            matrix[level].build();
            v.swap(zero);
            for(int i = 0; i < right; ++i){
                v[left + i] = one[i];
            }
        }
    }

    pair<int, int> succ(bool f, int l, int r, int level){
        return {matrix[level].rank(f, l) + mid[level] * f, matrix[level].rank(f, r) + mid[level] * f};
    }

    T access(int k){
        T ret = 0;
        for(int level = MAXLOG - 1; level >= 0; --level){
            bool f = matrix[level][k];
            if(f)   ret |= T(1) << level;
            k = matrix[level].rank(f, k) + mid[level] * f;
        }
        return ret;
    }

    T operator[](const int& k){
        return access(k);
    }

    int rank(const T& x, int r){
        int l = 0;
        for(int level = MAXLOG - 1; level >= 0; --level){
            tie(l, r) = succ((x >> level) & 1, l, r, level);
        }
        return r - l;
    }

    T kth_smallest(int l, int r, int k){
        assert(0 <= k && k < r - l);
        T ret = 0;
        for(int level = MAXLOG - 1; level >= 0; --level){
            int cnt = matrix[level].rank(false, r) - matrix[level].rank(false, l);
            bool f = cnt <= k;
            if(f){
                ret |= T(1) << level;
                k -= cnt;
            }
            tie(l, r) = succ(f, l, r, level);
        }
        return ret;
    }

    T kth_largest(int l, int r, int k){
        return kth_smallest(l, r, r - l - k - 1);
    }

    int range_freq(int l, int r, T upper){
        int ret = 0;
        for(int level = MAXLOG - 1; level >= 0; --level){
            bool f = ((upper >> level) & 1);
            if(f)   ret += matrix[level].rank(false, r) - matrix[level].rank(false, l);
            tie(l, r) = succ(f, l, r, level);
        }
        return ret;
    }

    int range_freq(int l, int r, T lower, T upper){
        return range_freq(l, r, upper) - range_freq(l, r, lower);
    }

    T prev_value(int l, int r, T upper){
        int cnt = range_freq(l, r, upper);
        return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1);
    }

    T next_value(int l, int r, T lower){
        int cnt = range_freq(l, r, lower);
        return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt);
    }
};

template<typename T, int MAXLOG>
struct CompressedWaveletMatrix {
    WaveletMatrix<int, MAXLOG> mat;
    vector<T> ys;

    CompressedWaveletMatrix(const vector<T>& v) : ys(v) {
        sort(begin(ys), end(ys));
        ys.erase(unique(ys.begin(), ys.end()), ys.end());
        vector<int> t(v.size());
        for(int i = 0; i < (int)v.size(); ++i)  t[i] = get(v[i]);
        mat = WaveletMatrix<int, MAXLOG>(t);
    }

    inline int get(const T& x){
        return lower_bound(begin(ys), end(ys), x) - begin(ys);
    }

    T access(int k){
        return ys[mat.access(k)];
    }

    T operator[](const int& k){
        return access(k);
    }

    int rank(const T& x, int r){
        auto pos = get(x);
        if(pos == ys.size() || ys[pos] != x)    return 0;
        return mat.rank(pos, r);
    }

    T kth_smallest(int l, int r, int k){
        return ys[mat.kth_smallest(l, r, k)];
    }

    T kth_largest(int l, int r, int k){
        return ys[mat.kth_largest(l, r, k)];
    }

    int range_freq(int l, int r, T upper){
        return mat.range_freq(l, r, get(upper));
    }

    int range_freq(int l, int r, T lower, T upper){
        return mat.range_freq(l, r, get(lower), get(upper));
    }

    T prev_value(int l, int r, T upper){
        auto ret = mat.prev_value(l, r, get(upper));
        return ret == -1 ? T(-1) : ys[ret];
    }

    T next_value(int l, int r, T lower){
        auto ret = mat.next_value(l, r, get(lower));
        return ret == -1 ? T(-1) : ys[ret];
    }
};

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

    int N, Q, l, r, x;
    cin >> N;
    vector<int> X(N);
    for(int i = 0; i < N; ++i)  cin >> X[i];
    CompressedWaveletMatrix<int, 25> cwm(X);
    cin >> Q;
    for(int q = 0; q < Q; ++q){
        cin >> l >> r >> x;
        --l;
        if(cwm.range_freq(l, r, x, x + 1)){
            cout << 0 << '\n';
        }
        else{
            int prv = cwm.prev_value(l, r, x);
            int nxt = cwm.next_value(l, r, x);
            int ans = INF;
            if(prv != -1)   chmin(ans, x - prv);
            if(nxt != -1)   chmin(ans, nxt - x);
            cout << ans << '\n';
        }
    }

    return 0;
}
0