Cod sursa(job #1412010)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 1 aprilie 2015 02:59:12
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct oaie{
    long long d;
    long long a;
}v[200100];
long long n,x,l,dh,i,j,nr,h[200100];
long long s;
FILE *f,*g;
long long cmp(oaie a,oaie b){
    return a.d<b.d;
}
void chg(long long &a,long long &b){
    long long aux=a;
    a=b;
    b=aux;
}
void heapins(long long n){
    long long c=dh;
    long long p=dh/2;
    while(p>=1){
        if(v[ h[c] ].a > v[ h[p] ].a){
            chg(h[c],h[p]);
            c=p;
            p/=2;
        }
        else
            break;
    }
}
void heapdel(){
    long long p=1;
    long long c=2;
    while(c<=dh){
        if( v[ h[c] ].a < v[ h[c+1] ].a && c+1<=dh )
            c++;
        if( v[ h[c] ].a > v[ h[p] ].a ){
            chg(h[c],h[p]);
            p=c;
            c*=2;
        }
        else
            break;
    }
}
int main(){
    f=fopen("lupu.in","r");
    g=fopen("lupu.out","w");
    fscanf(f,"%lld%lld%lld",&n,&x,&l);
    for(i=1;i<=n;i++){
        fscanf(f,"%lld%lld",&v[i].d,&v[i].a);
    }
    sort(v+1,v+n+1,cmp);
    nr=1;
    for(i=0;i<=x;i+=l){
        while(v[nr].d<=i&&nr<=n){
            dh++;
            h[dh]=nr;
            heapins(nr);
            nr++;
        }
        if(!dh)
            continue;
        s+=v[ h[1] ].a;
        chg(h[1],h[dh]);
        dh--;
        heapdel();
    }
    fprintf(g,"%lld",s);

    fclose(f);
    fclose(g);
    return 0;
}