Submission #1048452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048452		matere	Examination (JOI19_examination)	C++14	20 / 100	275 ms	26640 KiB

examination

#include<bits/stdc++.h>
using namespace std;
int n,q;
pair<int,int>a[100005];
vector<int>tree[400005];
void build(int v,int tl,int tr){
    for(int i=tl;i<=tr;i++) tree[v].push_back(a[i].second);
    sort(tree[v].begin(),tree[v].end());
    if(tl==tr) return;
    int mid=(tl+tr)/2;
    build(v*2,tl,mid);
    build(v*2+1,mid+1,tr);
}
int sum(int v,int tl,int tr,int l,int r,int val){
    if(l<=tl and tr<=r){
        int mr=lower_bound(tree[v].begin(),tree[v].end(),val)-tree[v].begin();
        // cout<<mr<<endl;
        return tree[v].size()-mr;
    }
    if(l>tr or tl>r){
        return 0;
    }
    int mid=(tl+tr)/2;
    return sum(v*2,tl,mid,l,r,val)+sum(v*2+1,mid+1,tr,l,r,val);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i].first>>a[i].second;
    }
    sort(a+1,a+n+1);
    build(1,1,n);
    int x,y,z;
    for(int i=1;i<=q;i++){
        int ans=0;
        cin>>x>>y>>z;
        int l=0,r=n+1;
        while(l+1<r){
            int mid=(l+r)/2;
            if(a[mid].first<x) l=mid;
            else r=mid;
        }
        if(r==n+1) cout<<0<<endl;
        else cout<<sum(1,1,n,r,n,y)<<endl;
    }
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:37:13: warning: unused variable 'ans' [-Wunused-variable]
   37 |         int ans=0;
      |             ^~~

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