Cod sursa(job #141933)

Utilizator sealTudose Vlad seal Data 23 februarie 2008 21:23:25
Problema Gardieni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
using namespace std;
#include<cstdio>
#include<algorithm>
#define Nm (1<<16)
int A[Nm],B[Nm],C[Nm],L[Nm],R[Nm],H[Nm],P[Nm],h,n,t;
long long ans;

void read()
{
    int i;

    freopen("gardieni.in","r",stdin);
    scanf("%d%d",&n,&t);
    for(i=0;i<n;++i)
        scanf("%d%d%d",A+i,B+i,C+i);
}

bool cmpl(int a, int b)
{
    return A[a]<A[b];
}

bool cmpr(int a, int b)
{
    return B[a]<B[b];
}

void sink(int x)
{
    int v=H[x],son=x<<1;

    while(son<=h)
    {
        if(son<h && C[H[son|1]]<C[H[son]])
            son|=1;
        if(C[v]<=C[H[son]])
            break;
        H[x]=H[son]; P[H[x]]=x;
        x=son; son<<=1;
    }
    H[x]=v; P[v]=x;
}

void lift(int x)
{
    int v=H[x];

    while(x>1 && C[v]<C[H[x>>1]])
    {
        H[x]=H[x>>1];
        P[H[x]]=x;
        x>>=1;
    }
    H[x]=v; P[v]=x;
}

void solve()
{
    int i,l=0,r=0;

    for(i=0;i<n;++i)
        L[i]=R[i]=i;
    sort(L,L+n,cmpl);
    sort(R,R+n,cmpr);

    for(i=1;i<=t;++i)
    {
        while(h && B[R[r]]==i-1)
        {
            H[P[R[r]]]=H[h];
            P[H[h--]]=P[R[r]];
            lift(P[R[r]]);
            sink(P[R[r]]);
            ++r;
        }
        while(l<n && A[L[l]]==i)
        {
            H[++h]=L[l];
            P[L[l]]=h;
            lift(h);
            ++l;
        }
        ans+=C[H[1]];
    }
}

void write()
{
    freopen("gardieni.out","w",stdout);
    printf("%lld\n",ans);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}