結果

問題 No.728 ギブ and テイク
ユーザー kyawa
提出日時 2021-12-31 16:22:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,464 ms / 3,000 ms
コード長 3,645 bytes
コンパイル時間 2,622 ms
コンパイル使用メモリ 218,164 KB
最終ジャッジ日時 2025-01-27 08:08:53
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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