Cod sursa(job #1798809)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 5 noiembrie 2016 14:17:07
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.5 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>

#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline long long nextnum(){
    long long a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}

#define MAXN 100000
class A{
    public:
    long long val[MAXN+1], val2[MAXN+1];
    int pos[MAXN+1];
    int heap[MAXN+1], last;

    inline int Heap_father(int p){
        return p/2;
    }
    inline int Heap_leftson(int p){
        return 2*p;
    }
    inline int Heap_rightson(int p){
        return 2*p+1;
    }
    inline void Heap_Swap(int p1, int p2){
        pos[heap[p1]]=p2;
        pos[heap[p2]]=p1;
        int aux=heap[p1];
        heap[p1]=heap[p2];
        heap[p2]=aux;
    }
    inline void Heap_upheap(int p){
        while(Heap_father(p)>0 && (val[heap[p]]>val[heap[Heap_father(p)]] || (val[heap[p]]==val[heap[Heap_father(p)]] && val2[heap[p]]>val2[heap[Heap_father(p)]]))){
            Heap_Swap(p, Heap_father(p));
            p=Heap_father(p);
        }
    }
    inline void Heap_downheap(int p){
        int flag=1;
        int ts=-1;
        while(flag){
            ts=-1;
            if(Heap_leftson(p)>last)
                flag=0;
            else{
                if(val[heap[Heap_leftson(p)]]>val[heap[p]])
                    ts=Heap_leftson(p);
                if(Heap_rightson(p)<=last && val[heap[Heap_rightson(p)]]>val[heap[Heap_leftson(p)]] && val[heap[Heap_rightson(p)]]>val[heap[p]])
                    ts=Heap_rightson(p);
                if(ts==-1)
                    flag=0;
                else{
                    Heap_Swap(p, ts);
                    p=ts;
                }
            }
        }
    }
    inline void Heap_insert(int poz){
        heap[++last]=poz;
        pos[poz]=last;
        Heap_upheap(last);
    }
    inline void Heap_erase(int poz){
        int p=pos[poz];
        Heap_Swap(p, last);
        last--;
        if(Heap_father(p)>0 && (val[heap[p]]>val[heap[Heap_father(p)]] || (val[heap[p]]==val[heap[Heap_father(p)]] && val2[heap[p]]>val2[heap[Heap_father(p)]])))
            Heap_upheap(p);
        else
            Heap_downheap(p);
    }
} H1;

#define MAXN 100000

struct Oaie{
    int d, a;
};
std::vector <Oaie> v[MAXN+1];
inline int min(int a, int b){
    return a < b ? a : b;
}
int main(){
    fi=fopen("lupu.in","r");
    fo=fopen("lupu.out","w");
    int n=nextnum();
    int x=nextnum(), l=nextnum();
    Oaie moarta;
    for(int i=0;i<n;i++){
        int d=nextnum(), a=nextnum();
        if(d<=x){
            int day=min(n, (x-d)/l+1);
            //printf("%d ", day);
            moarta.a=a;
            moarta.d=day;
            v[day].push_back(moarta);
        }
    }
    int ind=0;
    long long sum=0LL;
    for(int i=n;i>0;i--){
        for(int j=0;j<v[i].size();j++){
            H1.val[++ind]=v[i][j].a;
            H1.val2[ind]=v[i][j].d;
            H1.Heap_insert(ind);
        }
        if(H1.last!=0){
            sum+=H1.val[H1.heap[1]];
            H1.Heap_erase(H1.heap[1]);
        }
    }
    fprintf(fo,"%d", sum);
    fclose(fi);
    fclose(fo);
    return 0;
}