Cod sursa(job #1294725)

Utilizator japjappedulapPotra Vlad japjappedulap Data 18 decembrie 2014 01:19:14
Problema Lupul Urias si Rau Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;

#define PII pair<int,int>
#define x first
#define y second

ifstream is ("lupu.in");
ofstream os ("lupu.out");

int N, D, L, Pp, Bv, Sv;
unsigned long long sol;
PII v[100005];

struct Comp{ bool operator()(PII A, PII B){ return A.y < B.y; }};
priority_queue <PII, vector<PII>, Comp> Q;
inline int CMP(PII A, PII B) {return A > B;}

int main()
{
    is >> N >> D >> L;
    for (int i = 1; i <= N; ++i)
        is >> v[i].x >> v[i].y;
    sort(v+1, v+N+1, CMP);

    for (int i = 1; i <= N; )
        if (v[i].x + Pp*L <= D)
        {
            Bv = v[i].x + Pp*L;
            Sv = v[i].x + Pp*L - L + 1;
            for (; i <= N && Sv <= v[i].x + Pp*L && v[i].x + Pp*L <= Bv; ++i)
                Q.push(v[i]);
            while ( !Q.empty() && Q.top().x + Pp*L <= D)
            {
                sol += Q.top().y;
                Q.pop();
                Pp++;
            }
            for (; !Q.empty(); Q.pop());
        }
        else
            ++i;
    os << sol;

    is.close();
    os.close();
}