Cod sursa(job #769762)

Utilizator vendettaSalajan Razvan vendetta Data 20 iulie 2012 18:52:55
Problema Gardieni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("gardieni.in");
ofstream g("gardieni.out");
#define nmax 50006
#define tmax 1000005
#define x first
#define y second

int n, t, dr[tmax];
pair<int,pair<int,int> > v[nmax];
bool viz[tmax];

void citeste(){

    f >> n >> t;
    for(int i=1; i<=n; i++){
        int a, b, c;
        f >> a >> b >> c;
        v[i] = make_pair(c,make_pair(a,b));
    }

    sort(v+1, v+n+1);

}

void rezolva(){

    //dr[i] = poz, poz = pozitia primului element nevizitat

    for(int i=1; i<=t; i++) dr[i] = i;

    long long rez = 0;
    for(int i=1; i<=n; i++){
        int x = v[i].y.x;
        int y = v[i].y.y;
        for(int j=x; j<=y && j<=t;){
            int aux = dr[j] + 1;
            dr[j] = max(y,aux-1);
            if (viz[j]==0){
                rez += 1LL*v[i].x;
                viz[j] = 1;
            }
            j = aux;
        }
    }

    g << rez <<"\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();


}