#724678 (C++17) No.924 紲星

提出ソース

結果

問題	No.924 紲星
ユーザー	kyawa
提出日時	2021-12-17 18:23:00
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	6,042 bytes
コンパイル時間	3,505 ms
コンパイル使用メモリ	242,468 KB
実行使用メモリ	71,236 KB
最終ジャッジ日時	2024-09-14 19:46:05
合計ジャッジ時間	12,920 ms
ジャッジサーバーID （参考情報）	judge6 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,812 KB
testcase_03	AC	3 ms 6,812 KB
testcase_04	AC	3 ms 6,816 KB
testcase_05	AC	4 ms 6,940 KB
testcase_06	AC	3 ms 6,948 KB
testcase_07	AC	3 ms 6,944 KB
testcase_08	AC	1,026 ms 71,236 KB
testcase_09	AC	1,003 ms 71,236 KB
testcase_10	AC	998 ms 71,204 KB
testcase_11	AC	1,007 ms 71,200 KB
testcase_12	WA	-
testcase_13	AC	416 ms 29,824 KB
testcase_14	AC	349 ms 22,412 KB
testcase_15	AC	363 ms 25,348 KB
testcase_16	AC	550 ms 57,168 KB
testcase_17	AC	570 ms 33,060 KB
testcase_18	AC	2 ms 6,940 KB

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

ソースコード

raw source code

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

class WaveletMatrix{
public:
    long bitsize;
    vector<long> table_origin;
    vector<long> table_sorted;
    
    WaveletMatrix(vector<long> table) : table_origin(table){
        long table_max = *max_element(table.begin(), table.end());
        tablesize = table.size();
        bitsize = 0;
        while(table_max){
            bitsize++;
            table_max >>= 1;
        }
        assert(bitsize);
        matrix.resize(bitsize, vector<bool>(tablesize));
        zero_count.resize(bitsize, vector<long>(tablesize + 1, 0));
        for(long i = 0; i < bitsize; i++){
            for(long j = 0; j < tablesize; j++){
                matrix[i][j] = (table[j] >> (bitsize - i - 1)) & 1;
                if(not matrix[i][j]) zero_count[i][j + 1]++;
                zero_count[i][j + 1] += zero_count[i][j];
            }
            stable_sort(table.begin(), table.end(), [&](auto a, auto b){return ((a >> (bitsize - i - 1)) & 1) < ((b >> (bitsize - i - 1)) & 1);});
        }
        table_sorted = table;
    }
    
    long rank(long r, long x){
        //count x in [0, r)
        long L = 0; long R = r;//たぶんここLをlとして、引数にできる
        for(long level = 0; level < bitsize; level++){
            long same;//matrix[level][L, R)の中に、(x>>(bitsize-level-1)&1 と一致するのはいくつあるか?
            bool x_at_level = (x >> (bitsize - level - 1) & 1);
            if(x_at_level == 0){
                same = zero_count[level][R] - zero_count[level][L];
                L = zero_count[level][L]; R = L + same;
            }else{
                same = (R - zero_count[level][R]) - (L - zero_count[level][L]);
                L = zero_count[level][tablesize] + (L - zero_count[level][L]); R = L + same;
            }
        }
        return R - L;
    }
    
    long kth_min(long l, long r, long k/*0-indexed*/){
        long L = l; long R = r;
        for(long level = 0; level < bitsize; level++){
            auto [Lcount0, Lcount1] = counts(0, L, level);
            auto [count0, count1] = counts(L, R, level);
            if(k < count0){
                L = Lcount0;
                R = L + count0;
            }else{
                L = zero_count[level][tablesize] + Lcount1;
                R = L + count1;
                k -= count0;
            }
        }
        return table_sorted[L];
    }
    
    long range_freq(long l, long r, long lower, long upper){
        //count i s.t. l <= i < r and lower <= table[i] < upper
        return range_freq(l, r, upper) - range_freq(l, r, lower);
    }
    
private:
    vector<vector<bool>> matrix;
    vector<vector<long>> zero_count;//count 0 in matrix[i][0, r)
    long tablesize;
    
    pair<long,long> counts(long l, long r, long level){
        //{0の個数, 1の個数} in matrix[level][l, r)を返す
        return {zero_count[level][r] - zero_count[level][l], (r - zero_count[level][r]) - (l - zero_count[level][l])};
    }
    
    long range_freq(long l, long r, long upper){
        //count i s.t. l <= i < r and table[i] < upper
        if(upper >= (1 << bitsize)) return r - l;
        if(upper < 0) return 0;
        long res = 0;
        long L = l; long R = r;
        for(long level = 0; level < bitsize; level++){
            auto [Lcount0, Lcount1] = counts(0, L, level);
            auto [count0, count1] = counts(L, R, level);
            if(((upper >> (bitsize - level - 1)) & 1) == 0){
                //matrix[level][i] = 1　なら　必ず upper < table[i]
                L = Lcount0;
                R = L + count0;
            }else{
                //matrix[level][i] = 0　なら　必ず table[i] < upper
                res += count0;
                L = zero_count[level][tablesize] + Lcount1;
                R = L + count1;
            }
        }
        return res;
    }
};

class FenwickTree{
public:
    vector<long> table;
    long siz;
    FenwickTree(long siz) : table(siz + 1), siz(siz) {}
    long sum(long index){
        long res = 0;
        index++;//0-indexed to 1-indexed
        while(index > 0){
            res += table[index];
            index -= (index & -index);
        }
        return res;
    }
    void add(long index, long value){
        index++;//0-indexed to 1-indexed
        while(index < siz + 1){
            table[index] += value;
            index += (index & -index);
        }
    }
};

int main(){
    long N, Q; cin >> N >> Q;
    vector<long> A(N);
    for(long i = 0; i < N; i++) {
        cin >> A[i]; A[i] += 1000000000;
    }
    vector<long> acc(N + 1, 0);
    for(long i = 0; i < N; i++) acc[i+1] = acc[i] + A[i];
    WaveletMatrix wm(A);
    FenwickTree bit(N);
    vector<tuple<long,long,long,long>> query(Q);
    vector<long> res(Q);
    for(long i = 0; i < Q; i++){
        long l, r, mid;
        cin >> l >> r; l--; r--;
        mid = wm.kth_min(l, r+1, (r-l)/2);
        query[i] = {mid, l, r, i};    }
    sort(query.begin(), query.end());
    vector<pair<long,long>> AandI(N);
    for(long i = 0; i < N; i++) AandI[i] = {A[i], i};
    sort(AandI.begin(), AandI.end());
    long q = 0;
    for(long j = 0; j < N; j++){
        auto [a, i] = AandI[j];
        bit.add(i, a);
        while(q < Q and tuple<long,long,long,long>({a,0,0,0}) <= query[q] and query[q] <= tuple<long,long,long,long>({a,LONG_MAX,LONG_MAX,LONG_MAX})){
            auto [mid, l, r, res_i] = query[q];
            if(r - l == 0){
                res[res_i] = 0;
                q++;
                continue;
            }
            long sumoflessthanmid = bit.sum(r) - bit.sum(l-1) - mid;//ok
            long sumofgreaterthanmid = acc[r+1] - acc[l] - mid - sumoflessthanmid;
            long cntoflessthanmid = (r - l) / 2;//ok
            long cntofgreaterthanmid = r - l - cntoflessthanmid;//ok
            res[res_i] = (mid * cntoflessthanmid - sumoflessthanmid) + (sumofgreaterthanmid - mid * cntofgreaterthanmid);
            q++;
        }
    }
    for(long i = 0; i < Q; i++) cout << res[i] << '\n';
}

yukicoder

結果

テストケース

ソースコード