結果

問題 No.2161 Black Market
コンテスト
ユーザー Nachia
提出日時 2022-12-12 00:20:26
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,139 ms / 7,000 ms
コード長 6,957 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,031 ms
コンパイル使用メモリ 118,208 KB
最終ジャッジ日時 2025-02-09 09:51:07
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#line 1 "Main.cpp"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <atcoder/modint>
#line 2 "nachia\\multi-dimensional\\two-d-rectangle-query.hpp"

#line 4 "nachia\\multi-dimensional\\two-d-rectangle-query.hpp"
#include <cstdint>
#line 7 "nachia\\multi-dimensional\\two-d-rectangle-query.hpp"


namespace nachia{



template<class PosX, class PosY>
struct TwoDRectangleQuery{
private:

    struct BitVectorRank {
        using u64 = std::uint64_t;
        using u32 = std::uint32_t;

        static u32 popcountll(u64 c){
        #ifdef __GNUC__
            return __builtin_popcountll(c);
        #else
            c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
            c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
            c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
            c = (c * (~0ull/255)) >> 56;
            return c;
        #endif
        }
        
        std::vector<std::pair<u64, u32>> a;
        BitVectorRank(const std::vector<bool>& b = {}){
            int n = b.size();
            a.assign(n/64 + 1, std::make_pair((u64)0, (u32)0));
            auto p = b.begin();
            u32 sum = 0;
            u64 tmp = 0;
            for(int i=0; i<=n; i+=64){
                tmp = 0;
                int maxd = std::min<int>(n - i, 64);
                for(int d=0; d<maxd; d++){
                    tmp |= (u64)(*p ? 1 : 0) << d;
                    ++p;
                }
                a[i/64] = std::make_pair(tmp, sum);
                sum += popcountll(tmp);
            }
        }
        std::uint32_t rank(std::uint32_t i) const {
            auto [b, s] = a[i >> 6];
            return (u32)(popcountll(b & ~(~u64(0) << (i & 63)))) + s;
        }
        bool get(std::uint32_t i) const { return (a[i >> 6].first >> (i & 63)) & 1; }
    };
    
    int n;
    int N;
    int logN;
    std::vector<PosX> Xsorted;
    std::vector<PosY> Ysorted;
    std::vector<int> rankX;
    std::vector<std::vector<int>> Idx;
    std::vector<int> Z;
    std::vector<BitVectorRank> L;

public:

    TwoDRectangleQuery(const std::vector<std::pair<PosX, PosY>>& pos){
        n = pos.size();

        std::vector<int> sortIY(n);
        for(int i=0; i<n; i++) sortIY[i] = i;
        std::sort(sortIY.begin(),sortIY.end(),[&pos](int l,int r){ return pos[l].second<pos[r].second; });
        Ysorted.resize(n);
        for(int i=0; i<n; i++) Ysorted[i] = pos[sortIY[i]].second;

        std::vector<int> sortIX(n);
        rankX.resize(n);
        for(int i=0; i<n; i++) sortIX[i] = i;
        std::sort(sortIX.begin(),sortIX.end(),[&pos](int l,int r){ return pos[l]<pos[r]; });
        Xsorted.resize(n);
        for(int i=0; i<n; i++) Xsorted[i] = pos[sortIX[i]].first;
        for(int i=0; i<n; i++) rankX[sortIX[i]] = i;

        N = 1; logN = 0;
        while(N < n){ N *= 2; logN++; }
        Idx.assign(logN+1, std::vector<int>(n,-1));
        L.resize(logN);
        Z.resize(logN);
        for(int i=0; i<n; i++) Idx.back()[i] = sortIY[i];
        for(int i=logN-1; i>=0; i--){
            std::vector<bool> Lbuf(n,0);
            auto& preList = Idx[i+1];
            int z = ((n >> (i+1)) << i) + std::min(1<<i, (n % (2 << i)));
            Z[i] = z;
            int ai = 0, bi = z;
            for(int k=0; k<n; k++){
                bool chooseb = rankX[preList[k]] & (1<<i);
                if(!chooseb) Idx[i][ai++] = preList[k];
                else Idx[i][bi++] = preList[k];
                Lbuf[k] = !chooseb;
            }
            L[i] = BitVectorRank(Lbuf);
        }

        for(int i=0; i<n; i++) rankX[sortIY[i]] = i;
    }
 
    int get_segment_count() const { return Idx.size(); }
    int size() const { return n; }
    int to_vtx(int d, int i) const { return Idx[d][i]; }


    struct UpdatePoint{ int d, i; };

    std::vector<UpdatePoint> get_update_points(int v) const {
        std::vector<UpdatePoint> res(logN+1);
        int p = rankX[v];
        int d = logN;
        while(d > 0){
            res[d] = { d,p };
            d--;
            if(L[d].get(p)) p = L[d].rank(p);
            else p = Z[d] + p - L[d].rank(p);
        }
        res[d] = {d,p};
        return res;
    }


    struct Query{ int d,l,r; };
    std::vector<Query> get_ranges_from_idx(int xl, int xr, int yl, int yr){
        std::vector<Query> res;
        struct Search{ int i, xa, xb, ys, yt; };
        std::vector<Search> Q;
        res.reserve((logN+1)*2);
        Q.reserve((logN+1)*2);
        Q.push_back({ logN,0,n,yl,yr });
        for(int i=0; i<(int)Q.size(); i++){
            auto p = Q[i];
            if(p.xa == p.xb) continue;
            if(xr <= p.xa || p.xb <= xl) continue;
            if(xl <= p.xa && p.xb <= xr){
                res.push_back({ p.i, p.ys, p.yt });
                continue;
            }
            p.i--;
            int nxs = L[p.i].rank(p.ys), nxt = L[p.i].rank(p.yt);
            Q.push_back({ p.i,p.xa,p.xa+(1<<p.i),nxs,nxt });
            Q.push_back({ p.i,p.xa+(1<<p.i),p.xb,Z[p.i]+p.ys-nxs,Z[p.i]+p.yt-nxt });
        }
        return res; 
    }
  
    std::vector<Query> get_ranges(PosX xl, PosX xr, PosY yl, PosY yr){
        return get_ranges_from_idx(
            lower_bound(Xsorted.begin(),Xsorted.end(),xl) - Xsorted.begin(),
            lower_bound(Xsorted.begin(),Xsorted.end(),xr) - Xsorted.begin(),
            lower_bound(Ysorted.begin(),Ysorted.end(),yl) - Ysorted.begin(),
            lower_bound(Ysorted.begin(),Ysorted.end(),yr) - Ysorted.begin()
        );
    }
};

} // namespace nachia
#line 8 "Main.cpp"

using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;

using Modint = atcoder::static_modint<998244353>;



int main(){
    int N, K; cin >> N >> K;
    i64 L, P; cin >> L >> P;
    L++;
    vector<pair<i64, i64>> A(N);
    rep(i,N) cin >> A[i].first >> A[i].second;
    vector<vector<pair<i64,i64>>> S, T;
    S = T = {{{0,0}}};
    for(auto [xa,xb] : A){
        vector<vector<pair<i64,i64>>> tmp(S.size()+1);
        rep(s,S.size()) for(auto [a,b] : S[s]){
            tmp[s].emplace_back(a, b);
            tmp[s+1].emplace_back(a+xa, b+xb);
        }
        swap(S, tmp);
        swap(S, T);
    }

    i64 ans = 0;

    vector<pair<i64, i64>> Ssum;
    int Si = 0;
    for(int Ti=(int)T.size()-1; Ti>=0; Ti--){
        while(Ti + Si <= K && Si < (int)S.size()){
            copy(S[Si].begin(), S[Si].end(), back_inserter(Ssum));
            Si++;
        }
        auto TwoD = nachia::TwoDRectangleQuery<i64, i64>(Ssum);
        for(auto [a,b] : T[Ti]){
            for(auto q : TwoD.get_ranges(-INF, L-a, P-b, INF)) ans += q.r - q.l;
        }
    }

    cout << ans << '\n';
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0