#824815 (C++17) No.2161 Black Market

提出ソース

結果

問題	No.2161 Black Market
ユーザー	👑 Nachia
提出日時	2022-12-12 00:14:53
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	7,003 bytes
コンパイル時間	2,194 ms
コンパイル使用メモリ	122,596 KB
実行使用メモリ	24,180 KB
最終ジャッジ日時	2024-10-15 19:16:45
合計ジャッジ時間	9,381 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	RE	-
testcase_02	WA	-
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	RE	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	RE	-
testcase_19	WA	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	WA	-
testcase_26	RE	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	RE	-
testcase_31	RE	-
testcase_32	WA	-
testcase_33	RE	-
testcase_34	AC	6 ms 5,248 KB
testcase_35	AC	4 ms 5,248 KB
testcase_36	AC	48 ms 5,652 KB
testcase_37	RE	-
testcase_38	RE	-
testcase_39	WA	-

権限があれば一括ダウンロードができます

ソースコード

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>> Tsum;
    rep(Ti, T.size()){
        int Si = K - Ti;
        if(Si < 0) continue;
        if((int)S.size() > Si) Si = S.size()-1;
        copy(T[Ti].begin(), T[Ti].end(), back_inserter(Tsum));
        auto TwoD = nachia::TwoDRectangleQuery<i64, i64>(Tsum);
        for(auto [a,b] : S[Si]){
            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;

yukicoder

結果

テストケース

ソースコード