丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到n 编号。每家客栈都按照某一种色调进行装饰（总共 k 种，用整数 0 ~ k-1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。

两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 p。
他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p元的咖啡店小聚。

输入共n+1行。
第一行三个整数 n，k，p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；
接下来的 n行，第 i+1 行两个整数，之间用一个空格隔开，分别表示 i 号客栈的装饰色调和 i 号客栈的咖啡店的最低消费。 （c,v)
 

输出只有一行，一个整数，表示可选的住宿方案的总数。

输入输出样例说明：

客栈编号        1    2    3    4    5

色调                0    1    0    1    1

最低消费        5    3    2    4    5

 

2 人要住同样色调的客栈，所有可选的住宿方案包括：住客栈①③，②④，②⑤，④⑤，

但是若选择住 4、5 号客栈的话，4、5 号客栈之间的咖啡店的最低消费是 4，而两人能承受

的最低消费是 3 元，所以不满足要求。因此只有前 3 种方案可选。

数据范围：

30% n<=100

50% n<=1000

100% 2<=n<=200000, 0<k<=50, 0<=p<=100, 0<=最低消费<=100

 这道题O(kn)算法很简单啊，我来讲讲O（n）的算法吧

a[c]表示记录到第i个客栈为止色调为c的客栈的总数

b[c]表示记录到离当前客栈i最近的消费水平不高于p的客栈为止色调为c的客栈的数量

s[c]记录到当前客栈i为止，最后一个色调为c的客栈的编号

f记录距离客栈i最近的消费水平不超过p的客栈的编号

每读入一个客栈的色调c和最低消费v，我们首先来判断v是否超过了p，如果v没有超过p的话，我们让f=i，即先更新f。

 每读入一组数据c和v，我们就应该更新a[c]和s[c]，但是在这一步之前，我们要做如下操作：

不管当前客栈i的消费水平如何，我们来比较f和最后一个色调为c的客栈的编号s[c]的大小关系，

由于我们还没有更新s[c],所以这次比较不包含当前客栈i；

对于当前客栈i的色调c来说，如果该色调是在编号为f的客栈之后第一次出现，则必有f>=s[c]，那么a[c]里面记录的必然是在f客栈之前（包括f）色调为c的客栈的数量，这时我们让b[c]=a[c]，

如果色调c在客栈f之后出现的次数多于1次，那么我们必然已经更新过s[c]，那么必然有s[c]>f，这时我们不做任何操作，则b[c]内保存的依然是在客栈f之前（包括f）色调为c的客栈的数量。

在这里，f发生变化与否，对结果是没有影响的，因为即便在这一步之前f发生了变化，如果某个色调c一直没有出现的话，那对结果没有任何影响，

而一旦某个色调在f变化之后第一次出现，必然有f>=s[c]，这时必然要更新b[c]，那么b[c]必然在这里就会更新成为我们后面计算需要的正确的值，而且在f再次变化之前，b[c]将保持不变。

#include<cstdio>
int a[51],b[51],s[51],f=0,n,k,p,c,v,ans=0;
int main()
{
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&c,&v);
        if(v<=p)f=i;
        if(f>=s[c])b[c]=a[c];
        ans+=b[c];a[c]++;s[c]=i;
    }
    printf("%d",ans);
    return 0;
 }