Submission #1281321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281321		hanguyendanghuy	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	133 ms	14192 KiB

matryoshka

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
const ll MAXN=2e5+5,INF=1e18,MOD=1e9+7;
ll n,m,i,j,k,p,ans[MAXN],cnt;
ll dp[MAXN];
struct h{
	ll a,b,id;
} a[MAXN],query[MAXN];
bool cmp(h x,h y){
	if(x.b==y.b) return x.a>y.a;
	return x.b<y.b;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(i=1;i<=n;i++)
		cin>>a[i].a>>a[i].b;
	for(i=1;i<=m;i++)
		cin>>query[i].a>>query[i].b,query[i].id=i;
	sort(a+1,a+n+1,cmp);
	sort(query+1,query+m+1,cmp);
	ll cur=1,l=1;
	for(i=1;i<=m;i++){
		while(cur<=n&&a[cur].b<=query[i].b){
			ll p=upper_bound(dp+1,dp+l,-a[cur].a)-dp;
			dp[p]=-a[cur].a;
			if(p==l) l++;
			cur++;
		}
		ans[query[i].id]=upper_bound(dp+1,dp+l,-query[i].a)-dp-1;
	}
	for(i=1;i<=m;i++) cout<<ans[i]<<'\n';
}

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49