luoguP1311 选择客栈 题解(NOIP2011)

P1311 选择客栈  题目

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<ctime>
#define ll long long
#define rg register
#define N 200050
using namespace std;

int n,m,p;
ll ans;
struct house{
    int col,v;
}ljl[N];
int f[N][55],last[N];

inline int read()
{
    int s=0,m=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')m=-1,ch=getchar();
    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    return s*m;
}

void init()
{
    n=read();m=read();p=read();
    for(int i=1;i<=n;++i)
    {
        ljl[i].col=read();
        ljl[i].v=read();
    }
    int la=0;
    for(int i=1;i<=n;++i)
    {
        if(ljl[i].v<=p)la=i;
        for(int j=0;j<=50;++j)
        {
            f[i][j]=f[i-1][j];
        }
        last[i]=la;
        f[i][ljl[i].col]=f[i-1][ljl[i].col]+1;
    }
}

void work()
{
    for(int i=1;i<=n;++i)
    {
        ans+=f[last[i]][ljl[i].col];
        if(last[i]==i)ans--;
    }
}

int main()
{
    init();
    work();
    cout<<ans<<endl;
    return 0;
}