提出 #74603919

---

ソースコード 拡げる

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

struct Book {
    int s, d;
};

struct Query {
    int l, r, t, idx;
};

bool cmpBook(Book a, Book b) {
    return a.d > b.d;
}

bool cmpQuery(Query a, Query b) {
    return a.t > b.t;
}

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

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

    void update(int i, int val) {
        while(i <= n) {
            bit[i] += val;
            i += i & -i;
        }
    }

    int query(int i) {
        int sum = 0;
        while(i > 0) {
            sum += bit[i];
            i -= i & -i;
        }
        return sum;
    }

    int range(int l, int r) {
        return query(r) - query(l-1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    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;
    }

    vector<Query> queries(Q);
    for(int i = 0; i < Q; i++) {
        cin >> queries[i].l >> queries[i].r >> queries[i].t;
        queries[i].idx = i;
    }

    sort(books.begin(), books.end(), cmpBook);
    sort(queries.begin(), queries.end(), cmpQuery);

    Fenwick ft(N);
    vector<int> ans(Q);

    int i = 0;

    for(auto &q : queries) {
        while(i < M && books[i].d >= q.t) {
            ft.update(books[i].s, 1);
            i++;
        }

        int count = ft.range(q.l, q.r);
        ans[q.idx] = max(count - K, 0);
    }

    for(int x : ans) {
        cout << x << "\n";
    }

    return 0;
}

提出情報

ジャッジ結果