結果

問題 No.674 n連勤
ユーザー 00 Sakuda
提出日時 2025-08-24 01:37:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 94 ms / 2,000 ms
コード長 1,012 bytes
コンパイル時間 1,058 ms
コンパイル使用メモリ 100,668 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-24 01:37:36
合計ジャッジ時間 3,417 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <vector>
#include <iostream>

using namespace std;
using ll = long long;
#include <set>
#include <limits>
template<typename T>

struct RangeManage {
  set<pair<T, T>> ranges;
  pair<T, T> add(T l, T r) {
    T nl = l;T nr = r;
    while (true) {
      auto itr = ranges.lower_bound({l, -numeric_limits<T>::max()});
      if (itr == ranges.end()) break;
      if ((*itr).first > r+1) break;
      nr = max(nr, (*itr).second);
      ranges.erase(itr);
    }
    auto itr = ranges.lower_bound({l, numeric_limits<T>::max()});
    if (itr != ranges.begin()) {
      itr--;
      if ((*itr).second >= l-1) {
        nl = min(nl, (*itr).first);
        nr = max(nr, (*itr).second);
        ranges.erase(itr);
      }
    }
    ranges.insert({nl, nr});
    return {nl, nr};
  }

};
int main() {
  ll D;int Q;cin >> D >> Q;
  RangeManage<ll> Range;
  ll ret = 0;
  while (Q--) {
    ll a, b;cin >> a >> b;
    auto res = Range.add(a, b);
    ret = max(ret, res.second-res.first+1);
    cout << ret << endl;
  }
}
0