結果

問題 No.2161 Black Market
コンテスト
ユーザー AngrySadEight
提出日時 2022-11-23 15:00:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 771 ms / 7,000 ms
コード長 4,290 bytes
コンパイル時間 1,255 ms
コンパイル使用メモリ 105,004 KB
最終ジャッジ日時 2025-02-08 23:28:34
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
typedef long long ll;
using namespace std;
using pll = pair<ll,ll>;

struct BIT{
    //Binary Indexed Tree.
    ll N;
    vector<ll> vec;
    BIT(ll N_): N(N_), vec(N + 1){
        for (ll i = 0; i < N + 1; i++){
            vec[i] = 0;
        }
    }
    
    void add(ll p, ll x){
        if (p == 0){
            return;
        }
        for (ll i = p; i <= N; i += (i & -i)){
            vec[i] += x;
        }
    }

    ll sum(ll p){
        if (p == 0){
            return 0;
        }
        ll sum = 0;
        for (ll i = p; i > 0; i -= (i & -i)){
            sum += vec[i];
        }
        return sum;
    }
};

vector<vector<pll>> MakeVec(vector<pll> &vec){
    ll len = vec.size();
    vector<vector<pll>> ret(len + 1, vector<pll>(0));
    for (ll i = 0; i < (1 << len); i++){
        ll popcnt = 0;
        ll b = 0;
        ll a = 0;
        for (ll j = 0; j < len; j++){
            if ((i >> j) & 1){
                popcnt++;
                b += vec[j].first;
                a += vec[j].second;
            }
        }
        ret[popcnt].push_back(pll(b, a));
    }
    for (ll i = 0; i <= len; i++){
        sort(ret[i].begin(), ret[i].end());
    }
    return ret;
}

vector<ll> MakeUniqueA(vector<vector<pll>> &vec){
    vector<ll> ret(0);
    for (ll i = 0; i < vec.size(); i++){
        for (ll j = 0; j < vec[i].size(); j++){
            ret.push_back(vec[i][j].second);
        }
    }
    sort(ret.begin(), ret.end());
    ret.erase(unique(ret.begin(), ret.end()), ret.end());
    return ret;
}

int main(){
    ll N, K, L, P;
    cin >> N >> K >> L >> P;
    vector<ll> A(N);
    vector<ll> B(N);
    for (ll i = 0; i < N; i++){
        cin >> A[i] >> B[i];
    }
    vector<pll> p(N);
    for (ll i = 0; i < N; i++){
        p[i].first = A[i];
        p[i].second = B[i];
    }
    sort(p.begin(), p.end());
    for (ll i = 0; i < N; i++){
        A[i] = p[i].first;
        B[i] = p[i].second;
    }

    vector<pll> former(0);
    vector<pll> latter(0);
    for (ll i = 0; i < N / 2; i++) former.push_back(pll(B[i], A[i]));
    for (ll i = N / 2; i < N; i++) latter.push_back(pll(B[i], A[i]));

    vector<vector<pll>> former_vec = MakeVec(former);
    vector<vector<pll>> latter_vec = MakeVec(latter);

    vector<ll> former_a = MakeUniqueA(former_vec);
    vector<ll> latter_a = MakeUniqueA(latter_vec);

    //formerのほうを全探索する方針を取ることにする
    //そうすると，BITにはlatter_bの値（を座標圧縮した値）を追加することにしよう．

    unordered_map<ll, ll> mp_latter;
    for (ll i = 0; i < latter_a.size(); i++){
        mp_latter[latter_a[i]] = i + 1;
    }
    unordered_map<ll, ll> mp_former;
    for (ll i = 0; i < former_a.size(); i++){
        mp_former[former_a[i]] = i + 1;
    }

    vector<ll> idx(former_a.size());
    for (ll i = 0; i < former_a.size(); i++){
        if (former_a[i] + latter_a[latter_a.size() - 1] <= L){
            idx[i] = latter_a.size();
        }
        else if (former_a[i] + latter_a[0] > L){
            idx[i] = 0;
        }
        else{
            auto itr = upper_bound(latter_a.begin(), latter_a.end(), L - former_a[i]);
            idx[i] = itr - latter_a.begin();
        }
    }

    BIT bit((1 << 18) + 1);
    ll ans = 0;

    for (ll i = 0; i < former_vec.size(); i++){
        for (ll j = 0; j < latter_vec.size(); j++){
            if (i + j > K){
                continue;
            }
            ll now = latter_vec[j].size() - 1;
            for (ll k = 0; k < former_vec[i].size(); k++){
                while(now >= 0){
                    if (former_vec[i][k].first + latter_vec[j][now].first >= P){
                        bit.add(mp_latter[latter_vec[j][now].second], 1);
                        now--;
                    }
                    else{
                        break;
                    }
                }
                ll sm = bit.sum(idx[mp_former[former_vec[i][k].second] - 1]);
                ans += sm;
            }
            for (ll k = now + 1; k < latter_vec[j].size(); k++){
                bit.add(mp_latter[latter_vec[j][k].second], -1);
            }
        }
    }
    cout << ans << endl;

    return 0;
}
0