問題文の条件を言いかえると、
番目のパーティについて、以下のイベントが起こると考えてよいです。
- 日目からは毎日 個の飴を食べる
- 日目からは毎日 個の飴を食べる
よって、日にちの順にパーティのイベントを並び替えて、前から累積和を取ることによって、毎日 個以上の飴を食べる日が容易に分かります。
が十分大きい場合には、日にちごとに処理していては間に合わないため、前回のパーティのイベントとの日にちの差分を取る必要があります。
ソートがボトルネックとなるため、計算量は全体で となります。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m, k; cin >> n >> m >> k;
vector<int> l(m), r(m), c(m);
for(int i = 0; i < m; i++){
cin >> l[i] >> r[i] >> c[i];
}
vector<pair<int, int>> p;
for(int i = 0; i < m; i++){
p.push_back(make_pair(l[i], c[i]));
p.push_back(make_pair(r[i] + 1, -c[i]));
}
sort(p.begin(), p.end());
long long ans = 0, candy = 0, before = -1;
for(auto x : p){
if(candy >= k){
ans += x.first - before;
}
candy += x.second;
before = x.first;
}
cout << ans << endl;
}