Submission #154498

#	Time	Username	Problem	Language	Result	Execution time	Memory
154498		FiloSanza	Examination (JOI19_examination)	C++14	0 / 100	99 ms	6628 KiB

examination

#include <bits/stdc++.h>

using namespace std;

const int MAXX = 100010;

struct fenwick{
    int N;
    vector<int> v;
    fenwick(int sz){
        N = sz;
        v.resize(N+10, 0);
    }

    void update(int pos){
        if(pos < 0) return;
        for(pos+=2; pos<N; pos+=(pos&(-pos)))
            v[pos] ++;
    }

    int query(int pos){
        int ans = 0;
        for(pos+=2; pos>0; pos-=(pos&(-pos)))
            ans += v[pos];
        return ans;
    }

    int range(int a, int b){
        return query(b) - query(a-1);
    }
};

struct query_t{
    int a, b, c, idx, ans;
};

int main(){
    cin.tie(0);
    cin.sync_with_stdio(0);

    int N, M;
    cin >> N >> M;

    vector<pair<int, int>> v(N);
    for(auto &i : v) cin >> i.first >> i.second;
    v.push_back({-1, -1});
    sort(v.begin(), v.end());
    vector<query_t> q(M);
    for(int i=0; i<M; i++) q[i].idx = i, cin >> q[i].a >> q[i].b >> q[i].c;
    sort(q.begin(), q.end(), [](const query_t& a, const query_t& b){
        return a.a < b.a;
    });

    int pos = M-1;
    fenwick fen(MAXX);
    for(int i=N; i>=0 && pos >= 0; i--){
        fen.update(v[i].second);
        while(pos >= 0 && q[pos].a >= v[i].first){
            q[pos].ans = fen.range(q[pos].b, MAXX);
            pos--;
        }
    }

    sort(q.begin(), q.end(), [](const query_t& a, const query_t& b){
        return a.idx < b.idx;
    });

    for(auto i : q) cout << i.ans << "\n";
}

/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 0
10 10 0
60 60 0
0 100 0
*/

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57