Submission #46984602

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using int64 = long long;
using uint = unsigned int;
using uint64 = unsigned long long;
bool ckmin(auto& a, auto b) { return b < a ? a = b, 1 : 0; }
bool ckmax(auto& a, auto b) { return b > a ? a = b, 1 : 0; }
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  multiset<pair<int64, int64>> s;
  for (int i = 0; i < n; i++) {
    int64 t, d;
    cin >> t >> d;
    s.insert({t, t + d});
  }
  int64 last = 0;
  int ans = 0;
  multiset<int64> s2;
  while (!s.empty() || !s2.empty()) {
    debug(s, s2, last, ans);
    if (!s2.empty()) {
      auto t = *s2.begin();
      if (last + 1 <= t) {
        ans++;
        last++;
      }
      s2.erase(s2.begin());
    } else {
      last = s.begin()->first - 1;
    }
    while (!s.empty() && s.begin()->first <= last + 1) {
      s2.insert(s.begin()->second);
      s.erase(s.begin());
    }
  }
  cout << ans << '\n';

  return 0;
}

Submission Info

Judge Result