Cod sursa(job #1364918)

Utilizator touristGennady Korotkevich tourist Data 27 februarie 2015 21:31:42
Problema Gardieni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#include <algorithm>
#include <set>
#define Nmax 100015

using namespace std;

struct event
{
    int tip,cost,val;
    bool operator <(const event A) const
    {
        return val<A.val;
    }
} a[Nmax];

multiset <int> Q;

int main()
{
    int n,T,x,y,cost,i,len=0,p=1;
    long long sol=0;
    event w;
    freopen ("gardieni.in","r",stdin);
    freopen ("gardieni.out","w",stdout);
    scanf("%d%d", &n,&T);
    for(i=1;i<=n;++i)
    {
        scanf("%d%d%d", &x,&y,&w.cost);
        w.tip=1; w.val=x; a[++len]=w;
        w.tip=2; w.val=y+1; a[++len]=w;
    }
    sort(a+1,a+len+1);
    for(i=1;i<=T;++i)
    {
        while(p<=len && a[p].val==i)
        {
            if(a[p].tip==1) Q.insert(a[p].cost);
            else Q.erase(Q.find(a[p].cost));
            ++p;
        }
        sol+=*Q.begin();
    }
    printf("%lld\n", sol);
    return 0;
}