Cod sursa(job #1619741)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 28 februarie 2016 18:52:15
Problema Gardieni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
#define MAXT 1000000
#define MAXN 50005
#define INF 10000000
int v[MAXT+1],next[MAXT+1],A[MAXN],B[MAXN],C[MAXN];
inline void swap(int b,int e,int *v){
     int aux=v[b];
     v[b]=v[e];
     v[e]=aux;
}
void myqsort(int begin,int end){
     int b=begin,e=end,pivot=C[(b+e)/2];
     while(b<=e){
         while(C[b]<pivot) b++;
         while(C[e]>pivot) e--;
         if(b<=e){
             swap(b,e,A);
             swap(b,e,C);
             swap(b,e,B);
             b++;e--;
         }
     }
     if(begin<e) myqsort(begin,e);
     if(b<end) myqsort(b,end);
}
int find(int x){
    if(next[x]==0)
       return x;
    next[x]=find(next[x]);
    return next[x];
}
int main(){
    FILE*fi,*fout;
    int i,n,t,poz;
    long long s;
    fi=fopen("gardieni.in" ,"r");
    fout=fopen("gardieni.out" ,"w");
    fscanf(fi,"%d%d" ,&n,&t);
    for(i=0;i<n;i++)
        fscanf(fi,"%d%d%d" ,&A[i],&B[i],&C[i]);
    myqsort(0,n-1);
    for(i=1;i<=t;i++)
        v[i]=INF;
    for(i=0;i<n;i++){
        poz=find(A[i]);
        while(poz<=B[i]){
            v[poz]=C[i];
            next[poz]=B[i]+1;
            if(poz<t)
               poz=find(poz+1);
            else
               poz++;
        }
    }
    s=0;
    for(i=1;i<=t;i++)
       s=s+v[i];
    fprintf(fout,"%lld" ,s);
    fclose(fi);
    fclose(fout);
    return 0;
}