CSU 1685-Entertainment Box（set+二分）

E - Entertainment Box Time Limit:1000MS     Memory Limit:131072KB     64bit IO Format:%lld & %llu Submit  Status  Practice  CSU 1685

Description

Input

Output

Sample Input

3 1
1 2
2 3
2 3
4 1
1 3
4 6
7 8
2 5      
   

Sample Output

2
3      
    
#include<iostream>
#include<functional>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<set>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define T 100000 + 50

struct node
{
	ll L,R;
	bool operator<(const node& b)const{
		return R<b.R;
	}
}a[T];

struct line
{
	ll val;
	line():val(0){}
	line(ll _2):val(_2){}
	bool operator<(const line& b)const{
		return val>b.val;
	}
};

ll v[T];

bool cmp(const ll& a,const ll& b){return a>b;}

int main()
{
#ifdef zsc
	freopen("input.txt","r",stdin);
#endif
	int n,m,i,j;
	while(~scanf("%d%d",&n,&m))
	{
		ll c = 0;
		ll sum = 0;
		for(i=0;i<n;++i){
			scanf("%lld%lld",&a[i].L,&a[i].R);
		}
		if(m>=n){
			printf("%d\n",n);
			continue;
		}
		sort(a,a+n);
		fill(v,v+T,0);
		multiset< ll,greater<int> > Q;
		multiset< ll,greater<int> >::iterator it;
		ll k;
		Q.insert(a[0].R);
		c = 1;
		int cnt = 1;
		for(i=1;i<n;++i){
 			it = Q.begin();
			k = *it;
			it = Q.lower_bound(a[i].L);
			if(it==Q.end()&&cnt<m){
				c ++;cnt++;
				Q.insert(a[i].R);
			}
			else if(it!=Q.end()&&cnt<=m){
				c++;
				Q.erase(it);
				Q.insert(a[i].R);
			}
		}
		Q.clear();
		printf("%lld\n",c);
	}
	return 0;
}