Candy Party

2 secs 1024 MB

dyktr_06

Problem

Submissions

Test cases

Editorial

問題文の条件を言いかえると、
$i$ $( 1 \leq i \leq N)$ 番目のパーティについて、以下のイベントが起こると考えてよいです。

$L_i$ 日目からは毎日 $C_i$ 個の飴を食べる
$R_i + 1$ 日目からは毎日 $-C_i$ 個の飴を食べる

よって、日にちの順にパーティのイベントを並び替えて、前から累積和を取ることによって、毎日 $K$ 個以上の飴を食べる日が容易に分かります。
$N$ が十分大きい場合には、日にちごとに処理していては間に合わないため、前回のパーティのイベントとの日にちの差分を取る必要があります。

ソートがボトルネックとなるため、計算量は全体で $O(M \log M)$ となります。

#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;
}