Cod sursa(job #2464841)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 28 septembrie 2019 23:28:50
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <fstream>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>

#define d first
#define a second

using namespace std;

ifstream f("lupu.in");
ofstream g("lupu.out");

const int NMAX = 1e5 + 50;

int N;

long long X, L, ans = 0, Max = 0;

pair < long long, long long > A[NMAX];
long long Time[NMAX];

map < long long, vector < long long > > mp;
vector < long long > Keys;

priority_queue < long long > Q;

static inline long long Max_Moment (long long Val)
{
    if(Val > X)
        return 0;

    return 1LL * (1LL * (X - Val) / L + 1LL);
}

static inline void SpecialCase ()
{
    for(int i = 1; i <= N; ++i)
    {
        f >> A[i].d >> A[i].a;

        if(A[i].d <= X)
            ans += 1LL * A[i].a;
    }

    g << ans << '\n';

    return;
}

static inline void Read ()
{
    f.tie(NULL);

    f >> N >> X >> L;

    if(L == 0)
    {
        SpecialCase();

        exit(0);
    }

    for(int i = 1; i <= N; ++i)
    {
        f >> A[i].d >> A[i].a;

        Time[i] = Max_Moment(A[i].d);

        Max = max(Max,  Time[i]);

        if(Time[i] == 0)
            continue;

        mp[Time[i]].push_back(A[i].a);
    }

    return;
}

static inline bool cmp (int a, int b)
{
    return (a > b);
}

int main()
{
    Read();

    int Last = 0, i = 0;

    for(auto it : mp)
        Keys.push_back(it.first);

    sort(Keys.begin(), Keys.end(), cmp);

    if(Keys[(int)Keys.size() - 1] != 1)
        Keys.push_back(1);

    for(auto it : Keys)
    {
        if(i == 0)
        {
            Last = it;

            for(auto j : mp[it])
                Q.push(j);

            if(!Q.empty())
            {
                ans += 1LL * Q.top();
                Q.pop();
            }
        }
        else
        {
            if(Last - 1 >= it + 1 && !Q.empty())
            {
                for(int i = Last - 1; i >= it + 1 && !Q.empty(); --i)
                {
                    ans += 1LL * Q.top();

                    Q.pop();
                }
            }

            for(auto j : mp[it])
                Q.push(j);

            if(!Q.empty())
            {
                ans += 1LL * Q.top();
                Q.pop();
            }

            Last = it;
        }

        ++i;
    }

    g << ans << '\n';

    return 0;
}