Cod sursa(job #1615915)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 26 februarie 2016 22:51:17
Problema Gardieni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <cstdio>
#include <cctype>
#define BUF_SIZE 4096
#define MAXN 50005
#define MAXT 1000000
bool ok[MAXN];
int n, heap[MAXN], v[MAXN], poz[MAXN], val[2*MAXN+1], m, next[2*MAXN+1], lista[MAXT+2];
int pos=BUF_SIZE;
char buf[BUF_SIZE];
FILE *fin;
inline char nextch(){
    if(pos==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos=0;
    }
    return buf[pos++];
}
inline int read(){
    int x=0;
    char ch=nextch();
    while(!isdigit(ch)){
        ch=nextch();
    }
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=nextch();
    }
    return x;
}
inline void adauga(int x, int y){
    m++;
    val[m]=y;
    next[m]=lista[x];
    lista[x]=m;
}
inline int tata(int p){
    return (p-1)/2;
}
inline int fiust(int p){
    return 2*p+1;
}
inline int fiudr(int p){
    return 2*p+2;
}
inline void swap(int a, int b){
    int aux=heap[a];
    heap[a]=heap[b];
    heap[b]=aux;
    poz[heap[a]]=a;
    poz[heap[b]]=b;
}
inline void urcare(int p){
    if(p>=n)return ;
    while((p>0)&&(v[heap[p]]<v[heap[tata(p)]])){
        swap(p, tata(p));
        p=tata(p);
    }
}
inline void coborare(int p){
    int q, f=1;
    while((f)&&(fiust(p)<n)){
        q=fiust(p);
        if((fiudr(p)<n)&&(v[heap[fiudr(p)]]<v[heap[q]])){
            q=fiudr(p);
        }
        if(v[heap[q]]<v[heap[p]]){
            swap(p, q);
            p=q;
        }else{
            f=0;
        }
    }
}
int main(){
    int k, t, i, a, b, p, x;
    long long ans;
    FILE *fout;
    fin=fopen("gardieni.in", "r");
    fout=fopen("gardieni.out", "w");
    k=read();
    t=read();
    for(i=0; i<k; i++){
        a=read();
        b=read();
        v[i]=read();
        adauga(a, i);
        adauga(b+1, i);
    }
    n=0;
    ans=0;
    for(i=1; i<=t; i++){
        p=lista[i];
        while(p){
            if(ok[val[p]]){
                n--;
                x=heap[n];
                heap[poz[val[p]]]=x;
                poz[x]=poz[val[p]];
                urcare(poz[x]);
                coborare(poz[x]);
            }else{
                ok[val[p]]=1;
                heap[n]=val[p];
                poz[val[p]]=n;
                n++;
                urcare(n-1);
            }
            p=next[p];
        }
        ans+=v[heap[0]];
    }
    fprintf(fout, "%lld\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}