Cod sursa(job #2665154)

Utilizator OvidRata Ovidiu Ovid Data 30 octombrie 2020 10:35:48
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.63 kb
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int t, n, x, l;
pii o[100010];

ifstream fin("lupu.in"); ofstream fout("lupu.out");
#define cin fin
#define cout fout

struct mxheap{
    int hp[100010];
    int lt=0;
    void ins(int x){
        lt++; hp[lt]=x;
        int cr=lt;
        while(cr>1){
            if(hp[cr/2]<hp[cr]){
                swap(hp[cr/2], hp[cr]);
                cr/=2;
            }
            else{
                break;
            }
        }
    }

    void del(int crd){
        if(lt==crd){
            hp[lt]=0;
            lt--; return;
        }
        swap(hp[crd], hp[lt]); hp[lt]=0; lt--;
        //up-heapify
        int cr=crd;
        while(cr>1){
            if( hp[cr/2]<hp[cr] ){
                swap(hp[cr/2], hp[cr]);
                cr/=2;
            }
            else{
                break;
            }
        }

        //down-heapify

        while(cr<=lt){
            int a1=-1, a2=-1;
            if( (cr*2)<=lt){
                a1=hp[cr*2];
            }
            if((cr*2)<lt){
                a2=hp[cr*2+1];
            }
            if( ((a1>a2) && (a2>=0)) || ( (a1>=0) && (a2<0) )  ){
                if(a1>hp[cr]){
                    swap(hp[cr], hp[cr*2]);
                    cr*=2;
                }
                else{break;}
            }
            else{
                if(a2>hp[cr]){
                    swap(hp[cr], hp[cr*2+1]);
                    cr*=2; cr++;
                }
                else{
                    break;
                }
            }
        }

    }

};





int32_t main(){
INIT
cin>>n>>x>>l;
for(int i=1; i<=n; i++){
    cin>>o[i].ft>>o[i].sc;
}
sort(o+1, o+1+n);
int ac=-( (x-x%l)+(((x%l)>0)?(l):(0))  );
int ind=0;
int s=0;

mxheap hp;

while(ac<=0){
    if(hp.lt==0){
        ac+=( ( (o[ind+1].ft-(ac+x) )/l )*l+(  (((o[ind+1].ft-(ac+x) )%l)>0)?(l):(0) )  );
        if(ac>0){break;}
        while( ((ind+1)<=n) && (o[ind+1].ft<=(ac+x)) ){
            hp.ins(o[ind+1].sc ); ind++;
        }
    }
        s+=hp.hp[1];
        hp.del(1);
        ac+=l;
        if(ac>0){break;}
            while( ((ind+1)<=n) && (o[ind+1].ft<=(ac+x)) ){
            hp.ins(o[ind+1].sc ); ind++;
        }

}
cout<<s;

return 0;
}