Submission #715221

#	Time	Username	Problem	Language	Result	Execution time	Memory
715221		ismayil	Examination (JOI19_examination)	C++17	0 / 100	3026 ms	3776 KiB

examination

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 1e5;
int bit[MAX + 1];
void update(int pos, int val){
    for(int i = pos; i <= MAX; i += i & -i){
        bit[i] += val;
    }
}
int ask(int pos){
    int res = 0;
    for(int i = pos; i > 0; i -= i & -i){
        res += bit[i];
    }
    return res;
}
int ask(int l, int r){
    return ask(r) - ask(l - 1);
}
struct query{
    int x, y, idx;
    bool operator<(query other){
        return x > other.x;
    }
};
int main(){
    int n, m;
    cin>>n>>m;
    vector<pair<int, int>> p;
    for(int i = 0; i < n; i++){
        int x, y;
        cin>>x>>y;
        p.push_back({x, y});
    }
    sort(p.begin(), p.end());
    reverse(p.begin(), p.end());
    vector<query> queries;
    for(int i = 0; i < m; i++){
        int x, y, z;
        cin>>x>>y>>z;
        queries.push_back({x, y, i});
    }
    sort(queries.begin(), queries.end());
    int ans[m];
    int idx = 0;
    for (int i = 0; i < m; i++)
    {
        while(idx < n && queries[i].x <= p[idx].first){
            update(p[idx].second, 1);
            idx++;
        }
        ans[queries[i].idx] = ask(MAX) - ask(queries[i].y);
    }
    for (int i = 0; i < m; i++) cout<<ans[i]<<endl;
}

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