結果

問題 No.728 ギブ and テイク
ユーザー kyawakyawa
提出日時 2021-12-31 16:22:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,384 ms / 3,000 ms
コード長 3,645 bytes
コンパイル時間 2,988 ms
コンパイル使用メモリ 220,212 KB
実行使用メモリ 91,260 KB
最終ジャッジ日時 2024-04-17 04:19:06
合計ジャッジ時間 15,353 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 51 ms
8,192 KB
testcase_14 AC 91 ms
11,648 KB
testcase_15 AC 35 ms
6,912 KB
testcase_16 AC 78 ms
10,752 KB
testcase_17 AC 72 ms
10,240 KB
testcase_18 AC 968 ms
65,408 KB
testcase_19 AC 1,021 ms
69,504 KB
testcase_20 AC 1,222 ms
80,512 KB
testcase_21 AC 1,114 ms
72,960 KB
testcase_22 AC 415 ms
31,104 KB
testcase_23 AC 245 ms
21,376 KB
testcase_24 AC 776 ms
55,168 KB
testcase_25 AC 808 ms
54,912 KB
testcase_26 AC 391 ms
30,080 KB
testcase_27 AC 1,384 ms
91,260 KB
testcase_28 AC 874 ms
88,788 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class WaveletMatrix{
public:
    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 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;
    long bitsize;
    vector<long> table_origin;
    vector<long> table_sorted;
    
    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 < 0) return 0;
        if(upper >= (1L << bitsize)) return r - l;
        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;
    }
};

int main(){
    long res = 0;
    long N; cin >> N;
    vector<long> A(N); for(long i = 0; i < N; i++) cin >> A[i];
    for(auto &a : A) a += 1000000000;
    vector<long> AminusL(N), AplusR(N);
    for(long i = 0; i < N; i++){
        long L, R; cin >> L >> R;
        AminusL[i] = A[i] - L;
        AplusR[i] = A[i] + R;
    }
    WaveletMatrix wm(AminusL);
    for(long i = 0; i < N; i++){
        auto d = distance(A.begin(), upper_bound(A.begin(), A.end(), AplusR[i]));
        res += wm.range_freq(i + 1, d, 0, A[i] + 1);
    }
    cout << res << '\n';
}
0