Cod sursa(job #3260827)

Utilizator 0021592Grecu rares 0021592 Data 3 decembrie 2024 20:49:11
Problema Gardieni Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
ifstream in("gardieni.in");
ofstream out("gardieni.out");
int n, t, i, j, s, a, b, c, value[50010], current_time = 1;
struct crazy
{
    int time, ind;
    bool state;
};
vector<crazy> v;
bool sortfnc(crazy a, crazy b)
{
    if (a.time != b.time)
        return a.time < b.time;
    if (a.state != b.state)
        return a.state > b.state;
    return a.ind < b.ind;
}
set<pair<int, int>> q;
int32_t main()
{
    in >> n >> t;
    for (i = 1; i <= n; i++)
    {
        in >> a >> b >> c; value[i] = c;
        v.push_back({a, i, 0});
        v.push_back({b+1, i, 1});
    }
    sort(v.begin(), v.end(), sortfnc);
    while(j < v.size() && v[j].time == 1)
        q.insert(make_pair(value[v[j].ind], v[j].ind)),j++;
    while (j < v.size())
    {
        s += q.begin()->first * (v[j].time - current_time);
        current_time = v[j].time;
        if (!v[j].state)
            q.insert(make_pair(value[v[j].ind], v[j].ind)),j++;
        else
            q.erase(make_pair(value[v[j].ind], v[j].ind)),j++;
    }
    out << s;
    return 0;
}