Submission #2122262

---

Source Code Expand

#include<bits/stdc++.h> 
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
typedef long long ll;
using namespace std;
inline int read(){
	int n=0,f=1;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if (c=='-') c=getchar(),f=-1;
	for(;c>='0'&&c<='9';c=getchar()) n=n*10+c-48;
	return n*f;
}
const int maxn=2e5+5;
int n,m,i,j,ans;
struct ar{
	int l,r;
}a[maxn];
bool cmp(ar a,ar b){
	return (a.l==b.l)?a.r<b.r:a.l<b.l;
}
priority_queue<int>p;
bool bz[maxn];
int q[maxn],cnt;
int main(){
	n=read(),m=read();
	fo(i,1,n) a[i].l=read(),a[i].r=read();
	sort(a+1,a+1+n,cmp);
	j=1,ans=n;
	fo(i,1,n){
		if (j<=a[i].l&&j<=m) bz[j++]=1,ans--,p.push(-a[i].r);
		else{
			if (!p.empty()){
				int t=-p.top();
				if (t<a[i].r) p.pop(),p.push(-a[i].r),q[++cnt]=t;else
				q[++cnt]=a[i].r;
			}else q[++cnt]=a[i].r;
		}
	}
	sort(q+1,q+1+cnt);
	fd(i,m,1) if (bz[i]) break;else{
		for(;cnt&&i<q[cnt];cnt--);
		if (cnt) cnt--,ans--;else break;
	}
	printf("%d\n",ans); 
}

Submission Info

Judge Result