记录编号	468729	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]选择客栈	最终得分	100
用户昵称	爆零自动机	是否通过	通过
代码语言	C++	运行时间	0.287 s
提交时间	2017-11-01 21:30:38	内存使用	41.51 MiB

#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
#include <map>
#include <cstdlib>
#include <climits>
using namespace std;

#define maxn 200000+3
#define maxm 50+3

int n,m,p;
int cost[maxn];
int kz[maxm][maxn];
int clr,ans;

int find(int i,int l,int r,int key);//lower_pound()

int main()
{
	freopen("hotel.in","r",stdin);
	freopen("hotel.out","w",stdout);
	
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1; i<=n; i++)
	{
		scanf("%d%d",&clr,&cost[i]);
		kz[clr][0]++;//统计个数
		kz[clr][kz[clr][0]]=i; 
	}
	
	for(int i=0; i<=m; i++)
	{
		for(int j=1; j<kz[i][0]; j++)
		{
			for(int k=kz[i][j]; k<=kz[i][kz[i][0]]; k++)
			{
				if(cost[k]<=p)
				{
					if(kz[i][j]==k)
					{
						ans+=kz[i][0]-j;
					}
					else
					{
						int t=find(i,j,kz[i][0],k);
						ans+=kz[i][0]-t+1;
					}
					break;
				}
			}
		}
	}
	
	printf("%d\n",ans);
	
	return 0;
}
int find(int i,int l,int r,int key)
{
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(kz[i][mid]>=key)
		{
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	return l;
}