Cod sursa(job #2287075)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 21 noiembrie 2018 14:48:55
Problema Lupul Urias si Rau Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#pragma GCC optimize("03")
#include <bits/stdc++.h>
#define ll long long
#define PII pair < int , int >
#define MOD 1000000007
 
using namespace std;
 
ll n, m, l;

struct my {
    int pos, val;
};

my a[100100];

ll rs;
multiset < int > S;
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    ifstream cin("lupu.in");
    ofstream cout("lupu.out");
 
    cin >> n >> m >> l;

    ll r = m % l;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].pos >> a[i].val;

        if (a[i].pos <= r) S.insert(a[i].val);
    }

    if (S.size()) rs += *S.rbegin(), S.erase(S.find(*S.rbegin()));

    // cout << rs << " ";

    sort(a + 1, a + n + 1, [&](my a, my b){ return a.pos < b.pos; });

    int last = -1;
    for (int i = 1; i <= n; i++) {
        // cout << a[i].pos << "! ";
        if (a[i].pos <= r) continue;

        int inter = (a[i].pos - r) / l;
        int cp = inter;
        S.insert(a[i].val);

        while (i + 1 <= n && (a[i + 1].pos - r - 1) / l == cp) S.insert(a[i + 1].val), i++;

        while (S.size() && inter - last >= 1) rs += *S.rbegin(), S.erase(S.find(*S.rbegin())), inter--;
        // cout << inter << " " << rs << "\n";

        last = cp;
    }

    cout << rs;
    return 0;
}