Cod sursa(job #2877442)

Utilizator alexboat10759Alex Mateescu alexboat10759 Data 24 martie 2022 19:02:35
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda concursceva2 Marime 1.12 kb
#include <fstream>
#include <algorithm>

using namespace std;

struct oaie
{

  long long int poz;
  long long int val;

};

oaie v[100005];
long long int dq[100002];

bool cmp(oaie a, oaie b)
{
    if(a.poz < b.poz)
        return 1;

    return 0;
}

int main()
{
    ifstream cin("lupi.in");
    ofstream cout("lupi.out");

    long long int n, x, d;
    cin>>n>>x>>d;

    for(int i = 1; i <= n; i++)
    {
        cin>>v[i].poz>>v[i].val;
    }
    sort(v + 1, v + n + 1, cmp);
    v[n + 1].poz = x + 100;
    //for(int i = 1; i <= n; i++)
    //    cout<<v[i].poz<<" "<<v[i].val<<'\n';

    long long int lup = 0, rasp = 0;

    //cout<<'\n';
    int i = 0, st = 1, dr = 0;
    while(lup <= x && i <= n + 1)
    {
        i++;

        if(v[i].poz > lup)
        {
            //cout<<v[i - 1].poz<<" "<<v[i - 1].val<<" "<<lup<<'\n';
            rasp += dq[st];
            st++;
            lup = (v[i].poz / d + 1) * d;

        }
        while(st <= dr && v[i].val >= dq[dr])
            dr--;

        dr++;
        dq[dr] = v[i].val;
    }
    cout<<rasp;

    return 0;
}