結果

問題 No.728 ギブ and テイク
ユーザー shibh308shibh308
提出日時 2020-04-15 14:36:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,393 ms / 3,000 ms
コード長 3,104 bytes
コンパイル時間 3,144 ms
コンパイル使用メモリ 202,468 KB
最終ジャッジ日時 2025-01-09 19:16:04
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"

using namespace std;

using i64 = long long;


struct BitVector{
    vector<uint64_t> v;
    vector<int> r;
    BitVector(){}
    void build(){
        r.assign(v.size() + 1, 0);
        for(int i = 0; i < v.size(); ++i)
            r[i + 1] = r[i] + __builtin_popcountll(v[i]);
    }
    bool access(int x){
        return (v[x >> 6] >> (x & 63)) & 1;
    }
    // [0, x)の1の出現回数
    int rank(int x){
        return r[x >> 6] + __builtin_popcountll(v[x >> 6] & ((1uLL << (x & 63)) - 1));
    }
    int rank(int x, bool fl){
        return fl ? rank(x) : x - rank(x);
    }
};

template <typename T, int W>
struct WaveletMatrix{

    array<BitVector, W> bv;
    array<int, W> zero_cnt;

    WaveletMatrix(vector<T>& a){
        int n = a.size();
        vector<T> v(a);
        for(int i = W - 1; i >= 0; --i){
            vector<uint64_t> b((n >> 6) + 1, 0);
            vector<T> v1, v2;
            for(int j = 0; j < n; ++j){
                ((v[j] >> i) & 1 ? v2 : v1).push_back(v[j]);
                b[j >> 6] |= uint64_t((v[j] >> i) & 1) << (j & 63);
            }
            for(int j = 0; j < v.size(); ++j)
                v[j] = (j < v1.size() ? v1[j] : v2[j - v1.size()]);
            bv[i].v = move(b);
            bv[i].build();
            zero_cnt[i] = bv[i].rank(n, 0);
        }
    }

    // [l, r)内のxの数
    int count(int l, int r, T x){
        for(int i = W - 1; i >= 0; --i){
            bool fl = (x >> i) & 1;
            int st = bv[i].rank(l, fl);
            int en = bv[i].rank(r, fl);
            l = (fl ? zero_cnt[i] : 0) + st;
            r = (fl ? zero_cnt[i] : 0) + en;
        }
        return r - l;
    }

    // [l, r)内で[0, x)を満たす値の数
    int count_lower(int l, int r, T x){
        int cnt = 0;
        for(int i = W - 1; i >= 0; --i){
            bool fl = (x >> i) & 1;
            int st = bv[i].rank(l, fl);
            int en = bv[i].rank(r, fl);
            if(fl){
                st += zero_cnt[i];
                en += zero_cnt[i];
                cnt += (bv[i].rank(r, 0) - bv[i].rank(l, 0));
            }
            l = st, r = en;
        }
        return cnt;
    }

    // [l, r)内で[x, y)を満たす値の数
    int count_range(int l, int r, T x, T y){
        return count_lower(l, r, y) - count_lower(l, r, x);
    }
};


signed main(){

    int n;
    cin >> n;
    vector<i64> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        a[i] += 2000000000;
    }
    vector<i64> l(n), r(n);
    for(int i = 0; i < n; ++i){
        cin >> l[i] >> r[i];
        l[i] = a[i] - l[i];
        r[i] = a[i] + r[i];
    }

    WaveletMatrix<i64, 35> l_wm(l);
    WaveletMatrix<i64, 35> r_wm(r);

    i64 ans = 0;
    for(int i = 0; i < n; ++i){
        int l_idx = distance(a.begin(), lower_bound(a.begin(), a.end(), l[i]));
        int r_idx = distance(a.begin(), upper_bound(a.begin(), a.end(), r[i])) - 1;
        ans += r_wm.count_range(l_idx, i, a[i], (1LL << 34));
        ans += l_wm.count_range(i + 1, r_idx + 1, 0, a[i] + 1);
    }
    cout << (ans >> 1) << endl;

}
0