提出 #74607770

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

using ll=long long;

struct Fenwick {
    const int n;
    vector<int> bit;

    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    int sum(int idx) const {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }

    int rangeSum(int l, int r) const {
        return sum(r) - sum(l - 1);
    }
};

struct Book{
    int s,d;
};

struct Query{
    int l,r,t,id;
};
void solve(){
    int N,M,Q,K;
    cin>>N>>M>>Q>>K;
    vector<Book> books(M);
    for(int i=0;i<M;++i){
        cin>>books[i].s>>books[i].d;
    }
    ranges::sort(books, [](const auto& a,const auto& b){
        return a.d>b.d;
    });
    
    vector<Query> query(Q);
    for(int i=0;i<Q;++i){
        cin>>query[i].l>>query[i].r>>query[i].t;
        query[i].id=i;
    }
    ranges::sort(query, [] (const auto& a,const auto& b){
        return a.t>b.t;
    });

    Fenwick fen(N);
    int p=0;
    vector<int> ans(Q);
    for(auto&q:query){
        while(p<M&&books[p].d>=q.t){
            fen.add(books[p].s,1);
            ++p;
        }
        ans[q.id]=max(0,fen.rangeSum(q.l,q.r)-K);
    }
    for(auto&x:ans)cout<<x<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1; // cin>>t;
    while(t--) solve();
    return 0;
}

提出情報

ジャッジ結果