模拟(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;	
}