結果

問題 No.728 ギブ and テイク
ユーザー shibh308shibh308
提出日時 2020-04-15 14:36:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,358 ms / 3,000 ms
コード長 3,104 bytes
コンパイル時間 2,457 ms
コンパイル使用メモリ 203,540 KB
実行使用メモリ 23,512 KB
最終ジャッジ日時 2024-04-09 18:40:07
合計ジャッジ時間 14,286 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,948 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 3 ms
6,944 KB
testcase_11 AC 3 ms
6,940 KB
testcase_12 AC 4 ms
6,944 KB
testcase_13 AC 62 ms
6,940 KB
testcase_14 AC 102 ms
6,940 KB
testcase_15 AC 42 ms
6,940 KB
testcase_16 AC 93 ms
6,940 KB
testcase_17 AC 83 ms
6,944 KB
testcase_18 AC 932 ms
15,956 KB
testcase_19 AC 1,006 ms
16,968 KB
testcase_20 AC 1,188 ms
21,540 KB
testcase_21 AC 1,043 ms
17,612 KB
testcase_22 AC 390 ms
9,364 KB
testcase_23 AC 237 ms
6,944 KB
testcase_24 AC 762 ms
14,440 KB
testcase_25 AC 758 ms
14,400 KB
testcase_26 AC 372 ms
8,996 KB
testcase_27 AC 1,358 ms
23,448 KB
testcase_28 AC 1,230 ms
23,512 KB
testcase_29 AC 2 ms
6,940 KB
testcase_30 AC 2 ms
6,944 KB
testcase_31 AC 2 ms
6,944 KB
testcase_32 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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