Submission #19339982

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

typedef long long int ll;

int main() {
    ll n, c;
    cin >> n >> c;
    
    vector< pair<ll, ll> > events(n*2);
    for (int i = 0; i < n; i++) {
        ll ta, tb, tc; cin >> ta >> tb >> tc;
        events[i*2].first = ta;
        events[i*2].second = tc;
        events[i*2+1].first = tb + 1;
        events[i*2+1].second = -tc;
    }
    sort(events.begin(), events.end());
    ll primeFlg = false;
    ll ans = 0;
    ll prevPrice = 0;
    ll prevDay = -1;
    for (int i = 0; i < (int)events.size(); ) {
        ll d = (events[i].first - prevDay);
        prevDay = events[i].first;
        ans += primeFlg ? (d * c) : (d * prevPrice);
        while(events[i].first == prevDay) {
            prevPrice += events[i].second;
            if (prevPrice >= c) {
                primeFlg = true;
            } else {
                primeFlg = false;
            }
            i++;
        }
    }

    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result