#601141 (C++17) No.1332 Range Nearest Query

提出ソース

結果

問題	No.1332 Range Nearest Query
ユーザー	outline
提出日時	2021-01-08 22:23:51
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	6,972 bytes
コンパイル時間	1,643 ms
コンパイル使用メモリ	148,728 KB
実行使用メモリ	11,008 KB
最終ジャッジ日時	2024-04-28 03:43:46
合計ジャッジ時間	15,317 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	158 ms 10,880 KB
testcase_27	AC	200 ms 10,880 KB
testcase_28	AC	88 ms 5,376 KB
testcase_29	AC	88 ms 5,376 KB
testcase_30	AC	89 ms 5,376 KB
testcase_31	AC	83 ms 5,376 KB
testcase_32	AC	91 ms 5,376 KB
testcase_33	AC	89 ms 5,376 KB
testcase_34	AC	85 ms 5,376 KB
testcase_35	AC	86 ms 5,376 KB
testcase_36	AC	84 ms 5,376 KB
testcase_37	AC	89 ms 5,376 KB
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
testcase_47	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 + 2);
    for(int i = 0; i < N; ++i)  cin >> X[i];
    X[N] = -INF, X[N + 1] = INF * 2;
    CompressedWaveletMatrix<int, 10> 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;
}

yukicoder

結果

テストケース

ソースコード