Submission #964439

#	Time	Username	Problem	Language	Result	Execution time	Memory
964439		Unforgettablepl	Examination (JOI19_examination)	C++17	20 / 100	69 ms	10888 KiB

examination

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

#define int long long

int tree[100002];

int get(int x){
    int ans = 0;x++;
    while(x){
        ans+=tree[x];
        x-=x&-x;
    }
    return ans;
}

void add(int x){
    x++;
    while(x<=100001){
        tree[x]++;
        x+=x&-x;
    }
}

int ans[100001];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin >> n >> q;
    vector<pair<int,int>> students;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        students.emplace_back(x,y);
    }
    vector<tuple<int,int,int>> queries;
    for(int i=1;i<=q;i++){
        int a,b,c;cin>>a>>b>>c;
        queries.emplace_back(a,b,i);
    }
    sort(queries.rbegin(),queries.rend());
    sort(students.rbegin(),students.rend());
    auto iter = students.begin();
    for(auto[a,b,idx]:queries){
        while(iter!=students.end() and iter->first>=a){
            add(iter->second);
            iter++;
        }
        ans[idx] = get(100000)-get(b-1);
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}

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