Submission #3881561

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define fi first
#define sc second
#define pb push_back
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
#define N 200010
ll n,q,ans[N];
P d[N];
PP e[N];
int main(){
    cin>>n>>q;
    lol(i,n){
	ll a,b;cin>>a>>b;
	d[i].fi=-a,d[i].sc=b;
    }
    sort(d,d+n); d[n].fi=2e9,d[n].sc=2e9;
    lol(i,q){
	ll a,b;cin>>a>>b;
	e[i].fi.fi=-a,e[i].fi.sc=b;
	e[i].sc=i;
    }
    sort(e,e+n);
    
    vector<ll> lis; lis.pb(-1);
    ll j=0;
    lol(i,n+1){
	ll a=-d[i].fi,b=d[i].sc;
	for(;j<q&&-e[j].fi.fi>a;j++){
	    ll res=upper_bound(lis.begin(),lis.end(),e[j].fi.sc)-lis.begin();
	    ans[e[j].sc]=res-1;
	}
	auto it=upper_bound(lis.begin(),lis.end(),b);
	if(it==lis.end())lis.pb(b);
	else *it=b;
    }
    lol(i,q)cout<<ans[i]<<endl;
    return 0;
}

Submission Info

Judge Result