#include<bits/stdc++.h>
using namespace std;
int n,k,p,a[200010],b[200010],ans,st[200010][19],lg[200010];
vector<int>v[60];
int main()
{
	cin>>n>>k>>p;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
	}
	for(int i=1;i<=n;i++)
	{
		v[a[i]].push_back(i);
		st[i][0]=b[i];
	}
	lg[1]=0;
	for(int i=2;i<=n;i++)
	{
		lg[i]=lg[i>>1]+1;
	}
	for(int j=1;1<<j<=n;j++)
	{
		for(int i=1;i+(1<<j-1)<=n;i++)
		{
			st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
		}
	}
	for(int i=0;i<k;i++)
	{
		for(int j=0;j<v[i].size();j++)
		{
			for(int t=j+1;t<v[i].size();t++)
			{
				int l=v[i][j],r=v[i][t];
				int tp=lg[r-l+1];
				int minn=min(st[l][tp],st[r-(1<<tp)+1][tp]);
				if(minn<=p)
				{
					ans+=v[i].size()-t;
					break;
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

模拟(60pts)

枚举两个客栈,判断是否存在合法的中间客栈

#include<bits/stdc++.h>
using namespace std;
const int N=200010,M=55;
int a[N],b[N];
int sum[M];
int main()
{
    int n,k,p;
    cin>>n>>k>>p;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
    }
    int res=0;
    for(int i=1;i<=n;i++) //枚举第一个人的客栈
    {
        for(int j=i+1;j<=n;j++) //枚举第二个人的客栈
        {
            if(a[i]!=a[j]) continue; //色调不一样
            bool st=false;
            for(int k=i;k<=j;k++) //判断两个客栈之间是否有符合要求的咖啡店
            {
                if(b[k]<=p)
                {
                    st=true;
                }
            }
            if(st) res++;
        }
    }
    cout<<res;
    return 0;
}

双指针优化(O(n))

枚举右边的客栈,然后统计左边最近一个小于等于$p$的每个颜色的数目,根据右边客栈的价格进行分类讨论,如果右边客栈价格大于$p$,那么就是小于等于p左边相同色调的颜色的客栈数目,如果右边客栈价格小于等于$p$,那么可以直接算到当前位置,然后累加方案数目.

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=55;
typedef long long LL;
int a[N],b[N];
int sum[M];
int main()
{
	int n,k,p;
	cin>>n>>k>>p;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; 
	LL res=0;
	for(int i=1,j=0;i<=n;i++)
	{
		if(b[i]>p) res+=sum[a[i]]; //累加左边第一个小于等于p的颜色为a[i]的数目 
		else //当前价格可以 
		{
			while(j+1<=i)
			{
				j++;
				sum[a[j]]++;
			}
			res+=sum[a[i]]-1;//减去同一个房间的情况 
		}
	}
	cout<<res<<endl;
	return 0;	
}