Since he can start or stop Snuke Prime every day, it is optimal to apply for subscription if the total amount of payment will exceed \(C\) yen, and not use it if it does not.
Therefore, we want to find \(s[i]=\) ( The payment for the \(i\)-th day without Snuke Prime ).

If the range of \(i\) is small enough, we can calculate it with cumulative sums; however, this time, the range of \(i\) is large, so we have to find a different way.
For example, the following method will work.

A \(c_i\)-yen service from the \(a_i\)-th day to the \(b_i\)-th day can be regarded as:

• an event where the cost increases by \(c_i\) yen between the \((a_i - 1)\)-th day and the \(a_i\)-th day, and
• an event where the cost decreases by \(c_i\) yen between the \(b_i\)-th day and the \((b_i + 1)\)-th day.

Sort those events on the time base.
Then, inspect the events one by one in order, while updating two variables “current date” and “current price”, so that the problem can be solved in a total of \(O(N\log N)\) time.

Also, we can compress the coordinates so that we can calculate cumulative sums.

Sample Code (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

int main(){
    ll N, C;
    cin >> N >> C;
    vector<pair<ll, ll>> event;
    for(ll i = 0; i < N; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        event.emplace_back(a - 1, c);
        event.emplace_back(b, -c);
    }
    sort(event.begin(), event.end());
    ll ans = 0, fee = 0, t = 0;
    for(auto [x, y] : event){
        if(x != t){
            ans += min(C, fee) * (x - t);
            t = x;
        }
        fee += y;
    }
    cout << ans << endl;
}

Sample Code (Python)

N, C = map(int, input().split())
event = []
for i in range(N):
    a, b, c = map(int, input().split())
    a -= 1
    event.append((a, c))
    event.append((b, -c))

event.sort()
ans = 0
fee = 0
t = 0
for x, y in event:
    if x != t:
        ans += min(C, fee) * (x - t)
        t = x
    fee += y

print(ans)