Cod sursa(job #3198588)

Utilizator Allie28Radu Alesia Allie28 Data 29 ianuarie 2024 20:12:36
Problema Lupul Urias si Rau Scor 88
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");

const int LMAX = 100005;
priority_queue<int> Q;
struct interval{
    int st, dr;
    bool operator < (interval b) {
        if (st < b.st) return true;
        else if (st == b.st && dr > b.dr) return true;
        return false;
    }
}v[LMAX];

int main() {
    int n, i, x, l;
    fin>>n>>x>>l;
    for (i = 0; i < n; i++) {
        fin>>v[i].st>>v[i].dr;
        v[i].st = (x - v[i].st)/l + 1; //dupa cate atacuri oaia iese din raza lupului
    }
    sort(v, v + n);
    long long lana = 0; //distanta parcursa de oi
    int currsizeQ = 1;
    i = 0;
    while (i < n) {
        Q.push(-v[i].dr);
        i++;
        while (i < n && v[i].st == currsizeQ) {
            if (-Q.top() < v[i].dr) {
                Q.pop();
                Q.push(-v[i].dr);
            }
            i++;
        }
        currsizeQ++;
    }
    while (!Q.empty()) {
        lana = lana - Q.top();
        Q.pop();
    }
    fout<<lana;

    fin.close();
    fout.close();
    return 0;
}