Cod sursa(job #2974419)

Utilizator VmanDuta Vlad Vman Data 4 februarie 2023 08:02:53
Problema Gardieni Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int n, t, a, b, c;
vector<pair<int,int> > v;
vector<int> cur;

int main() {
    freopen("gardieni.in", "r", stdin);
    freopen("gardieni.out", "w", stdout);
    
    cin >> n >> t;
    for (int i = 0; i < n; ++i) {
        cin >> a >> b >> c;
        v.push_back(make_pair(a, c));
        v.push_back(make_pair(b, 0));
        v.push_back(make_pair(b + 1, -c));
    }
    
    sort(v.begin(), v.end());
    int prev = 0;
    long long sol = 0;
    for (int i = 0; i < v.size();) {
        if (v[i].first > t) {
            break;
        }
            
        int j = i;
        while (j < v.size() && v[j].first == v[i].first) {
            if (v[j].second > 0) {
                cur.push_back(v[j].second);
            } else {
                for (int k = 0; k < cur.size(); ++k) {
                    if (cur[k] == -v[j].second) {
                        //cout << "pop " << v[j].first << " " << cur[k] << endl;
                        cur[k] = cur[cur.size() - 1];
                        cur.pop_back();
                        break;
                    }
                }
            }
            ++j;
        }
        
        int best = 2000000000;
        for (auto it : cur) {
            best = min(best, it);
        }
        
        //cout << prev << " " << v[i].first << " " << best << endl;
        sol += (long long)(v[i].first - prev) * best;
        prev = v[i].first;
        
        i = j;
    }
    
    cout << sol << "\n";
    
    return 0;
}