Submission #3019749

---

Source Code Expand

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define M 200200
#define mid (l+r>>1)
using namespace std;
int read(){
    int nm=0,fh=1;char cw=getchar();
    for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;
    for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
    return nm*fh;
}
int n,m,ans,f[M],cnt,vis[M],last;
int fd(int x){return x==f[x]?x:f[x]=fd(f[x]);}
struct op{
    int L,R,id;
    void gtin(int x){L=read(),R=read(),id=x;}
    bool operator <(const op&ot)const{return R==ot.R?L>ot.L:R>ot.R;}
}t[M];
bool cmpL(op i,op j){return i.L<j.L;}
bool cmpR(op i,op j){return i.R<j.R;}
priority_queue<op> Q;
void del(int x,int maxn){
	x=fd(x);
	if(x<=maxn) f[x]=fd(x+1);
	else ans++;
}
int main(){
    n=read(),m=read(),f[0]=0,f[m+1]=m+1;
    for(int i=1;i<=n;i++) t[i].gtin(i);
    sort(t+1,t+n+1,cmpL),last=1;
    for(int i=1;i<=n;i++){
    	if(last<=t[i].L){last++,Q.push(t[i]);continue;}
		Q.push(t[i]); Q.pop();
	}
    for(int i=1;i<=m;i++) f[i]=i;
	while(!Q.empty()) vis[Q.top().id]=1,Q.pop();
	for(int i=1;i<=n;i++) if(vis[t[i].id]) del(1,t[i].L);
	sort(t+1,t+n+1,cmpR);
	for(int i=1;i<=n;i++) if(!vis[t[i].id]) del(t[i].R,m);
    printf("%d\n",ans);
    return 0;
}

Submission Info

Judge Result