[HOJ] 336 - 廷廷的大秘寶

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
struct T{
    int x,k;
    friend bool operator < (T a,T b){
        return a.x<b.x;
    }
}out;
priority_queue<T> que;
struct P{
    int x,y,r,k;
};
vector<P> arr;
int cmp(P a,P b){
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y>b.y;
}
int is[100005]={0};
int main(){
    int n,m,i,j,x,y,add=0,ans=0;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++){
        scanf("%d%d",&x,&y);
        arr.push_back((P){x,1,y,i});
        arr.push_back((P){y,-1,y,i});
    }
    sort(arr.begin(),arr.end(),cmp);
    for(i=0;i<n*2;i++){
        if(arr[i].y==1){
            add++;
            que.push((T){arr[i].r,arr[i].k});
        }
        else if(is[arr[i].k]==0) add--;
        //printf("%d..",add);
        if(add==m){
            ans++;
            add--;
            out=que.top();
            que.pop();
            //printf(",,%d,,",que.size());
            is[out.k]=1;
        }
    }
    printf("%d\n",ans);
}