Cod sursa(job #2554535)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 23 februarie 2020 01:28:22
Problema Lupul Urias si Rau Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <fstream>
using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

const int N = 100000;

struct oaie{
    int dist, lana;
} oi[N];

int h[N+1], grupa[N+1], used[N+1];
int nh;

void schimba(int p, int q){
    swap(h[p], h[q]);
}

bool compare(int p, int q){
    if(oi[h[p]].lana > oi[h[q]].lana)
        return true;
    else if(oi[h[p]].lana == oi[h[q]].lana && grupa[h[p]] > grupa[h[q]])
        return true;
    return false;
}

void urca(int p){
    while(p>1 && compare(p, p/2)){
        schimba(p, p/2);
        p /= 2;
    }
}

void coboara(int p){
    int fs = 2*p;
    int fd = 2*p+1;
    int bun = p;
    if(fs <= nh && compare(fs, bun))
        bun = fs;
    if(fd <= nh && compare(fd, bun))
        bun = fd;
    if(bun != p){
        schimba(p, bun);
        coboara(bun);
    }
}

void adauga(int x){
    h[++nh] = x;
    urca(nh);
}

void sterge(int p){
    schimba(p, nh--);
    urca(p);
    coboara(p);
}

bool cmp(oaie a, oaie b){
    if(a.dist < b.dist)
        return true;
    return false;
}

int main()
{
    int n,x,l,i,gr,timp,added;
    long long lana;
    fin >> n >> x >> l;
    for(i=0; i<n; i++)
        fin >> oi[i].dist >> oi[i].lana;
    sort(oi, oi+n, cmp);
    while(n>=0 && oi[n-1].dist > x)
        n--;
    gr = 0;
    timp = 0;
    added = 0;
    for(i=0; i<n; i++){
        if(oi[i].dist <= timp){
            added++;
            grupa[i] = gr;
            adauga(i);
        }
        else{
            timp += l;
            if(added > 0)
                gr++;
            added = 0;
            i--;
        }
    }
    for(i=0; i<n; i++)
        grupa[i] = gr - grupa[i] + 1;
    lana = 0;
    for(i=0; i<=gr; i++){
        while(used[grupa[h[1]]] + i > grupa[h[1]])
            sterge(1);
        lana = lana + 1LL*oi[h[1]].lana;
        used[grupa[h[1]]]++;
        sterge(1);
    }
    fout << lana;
    return 0;
}