选择客栈

分析

对于每种颜色单独考虑，从左往右扫，记录最后出现的小于 p 的位置，对于贡献，我们枚举右端点，当记录的位置大于前一次出现的的位置时，更新可用左端点的数量。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+7;
const int M = 1e9+7;

int a[maxn],b[maxn],cnt[maxn],lst[maxn],tot[maxn];

signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    int n,k,p;
    cin>>n>>k>>p;
    for(int i = 1; i <= n; i++) 
    {
        cin>>a[i]>>b[i];
    }
    int ans = 0,r = 0;
    for(int i = 1; i <= n; i++) 
    {
        if(b[i] <= p) r = i;
        if(r >= lst[a[i]]) tot[a[i]] = cnt[a[i]];
        lst[a[i]] = i;
        ans += tot[a[i]];
        cnt[a[i]]++;
    }
    cout<<ans<<endl;
    return 0;
}