結果

問題 No.1471 Sort Queries
ユーザー Ricky_ponRicky_pon
提出日時 2021-04-09 21:49:29
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 3,263 bytes
コンパイル時間 2,341 ms
コンパイル使用メモリ 207,896 KB
実行使用メモリ 4,636 KB
最終ジャッジ日時 2023-09-07 10:50:08
合計ジャッジ時間 4,453 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,384 KB
testcase_02 AC 1 ms
4,384 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,384 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 4 ms
4,380 KB
testcase_14 AC 4 ms
4,380 KB
testcase_15 AC 5 ms
4,380 KB
testcase_16 AC 3 ms
4,380 KB
testcase_17 AC 4 ms
4,380 KB
testcase_18 AC 3 ms
4,384 KB
testcase_19 AC 3 ms
4,384 KB
testcase_20 AC 5 ms
4,380 KB
testcase_21 AC 4 ms
4,380 KB
testcase_22 AC 4 ms
4,380 KB
testcase_23 AC 7 ms
4,384 KB
testcase_24 AC 7 ms
4,380 KB
testcase_25 AC 9 ms
4,636 KB
testcase_26 AC 7 ms
4,380 KB
testcase_27 AC 9 ms
4,400 KB
testcase_28 AC 8 ms
4,384 KB
testcase_29 AC 7 ms
4,380 KB
testcase_30 AC 7 ms
4,380 KB
testcase_31 AC 9 ms
4,380 KB
testcase_32 AC 9 ms
4,384 KB
testcase_33 AC 10 ms
4,408 KB
testcase_34 AC 11 ms
4,412 KB
testcase_35 AC 12 ms
4,380 KB
testcase_36 AC 8 ms
4,404 KB
testcase_37 AC 8 ms
4,420 KB
testcase_38 AC 9 ms
4,480 KB
testcase_39 AC 9 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define For(i, a, b) for (int(i) = (int)(a); (i) < (int)(b); ++(i))
#define rFor(i, a, b) for (int(i) = (int)(a)-1; (i) >= (int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second

using namespace std;

typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;

template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
T div_floor(T a, T b) {
    if (b < 0) a *= -1, b *= -1;
    return a >= 0 ? a / b : (a + 1) / b - 1;
}
template <class T>
T div_ceil(T a, T b) {
    if (b < 0) a *= -1, b *= -1;
    return a > 0 ? (a - 1) / b + 1 : a / b;
}

template <typename T>
struct coord_comp {
    vector<T> v;
    bool sorted = false;

    coord_comp() {}

    int size() { return v.size(); }

    void add(T x) { v.push_back(x); }

    void build() {
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        sorted = true;
    }

    int get_idx(T x) {
        assert(sorted);
        return lower_bound(v.begin(), v.end(), x) - v.begin();
    }
};

constexpr lint mod = 1000000007;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

struct bit_vector {
    vector<int> v;

    bit_vector() {}

    bit_vector(vector<int> &a, int d) {
        v.resize(a.size() + 1, 0);
        rep(i, a.size()) v[i + 1] = (a[i] >> d) & 1;
        partial_sum(v.begin(), v.end(), v.begin());
    }

    int count(int i, int x) { return x ? v[i] : i - v[i]; }

    void print_vector() {
        for (auto x : v) printf("%d ", x);
        printf("\n");
    }
};

template <int w = 31>
struct wavelet_matrix {
    int n;
    array<bit_vector, w> v;

    wavelet_matrix(vector<int> a) : n(a.size()) {
        vector<vector<int>> b(2, vector<int>(n));
        copy(a.begin(), a.end(), b[(w + 1) & 1].begin());
        rrep(i, w) {
            v[i] = {b[i & 1], i};
            int l = 0, r = n - 1;
            rep(j, n) {
                if ((b[i & 1][j] >> i) & 1)
                    b[(i + 1) & 1][r--] = b[i & 1][j];
                else
                    b[(i + 1) & 1][l++] = b[i & 1][j];
            }
            reverse(b[(i + 1) & 1].begin() + l, b[(i + 1) & 1].end());
        }
    }

    int quantile(int l, int r, int K) {
        int ret = 0;
        rrep(i, w) {
            int lz = v[i].count(l, 0), rz = v[i].count(r, 0), cntz = rz - lz;
            if (cntz > K) {
                l = lz;
                r = rz;
            } else {
                ret |= 1 << i;
                K -= cntz;
                int t = v[i].count(n, 0);
                l = t + l - lz;
                r = t + r - rz;
            }
        }
        return ret;
    }
};

int main() {
    int n, q;
    string s;
    cin >> n >> q >> s;

    vector<int> a(n);
    rep(i, n) a[i] = s[i];
    wavelet_matrix wm(a);
    rep(_, q) {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        --l;
        --x;
        printf("%c\n", wm.quantile(l, r, x));
    }
}
0