记录编号	329329	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]选择客栈	最终得分	100
用户昵称	123	是否通过	通过
代码语言	C++	运行时间	1.232 s
提交时间	2016-10-25 08:27:49	内存使用	94.17 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int ya[200000]={0},yb[200000]={0},q[60][200015]={0},ans;
int qw[60][200035]={0},zan[100]={0},yd[200035]={0};
int main(){
	freopen ("hotel.in","r",stdin);
	freopen ("hotel.out","w",stdout);
	int a,b,c,e,d,f,g,h;
	int n,k,p;
	int x,y,z;
	cin>>n>>k>>p;
	ans=0;
	h=0;
	for (a=1;a<=n;a++)
	{
		cin>>ya[a]>>yb[a];
	}
	for (x=0;x<=k-1;x++)
	{
		z=0;
		for (y=1;y<=n;y++)
		{
			if(ya[y]==x)
			{
				z=z+1;
			}
			qw[x][y]=z;
		}
	}
	
	for (x=1;x<=n;x++)
	{
		if(yb[x]<=p)
		yd[x+1]=x;
		else
		yd[x+1]=yd[x];
	}
	for (b=2;b<=n;b++)
	{
		h=0;
		if(yb[b]<=p)
		{
			if(yd[b]!=0)
			h=h+qw[ya[b]][b]-1;
		}
		if(yb[b]>p)
		{
			if(qw[ya[b]][yd[b]]!=0)
			{
				h=qw[ya[b]][yd[b]];
			}
		}
		q[ya[b]][b]=q[ya[b]][b-1]+h;
		for (f=0;f<=k-1;f++)
		{
			if(h!=0)
			{
				if(f!=ya[b])
				q[f][b]=q[f][b-1];
			}
			else
			{
				q[f][b]=q[f][b-1];
			}

		}
	}
	for (g=0;g<=k-1;g++)
	{
		ans=ans+q[g][n];
	}
	cout<<ans;
	return 0;
}