結果
問題 | No.674 n連勤 |
ユーザー |
![]() |
提出日時 | 2020-11-15 20:54:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 23 ms / 2,000 ms |
コード長 | 2,079 bytes |
コンパイル時間 | 679 ms |
コンパイル使用メモリ | 78,708 KB |
最終ジャッジ日時 | 2025-01-16 01:03:19 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <map>#include <utility>// CUT begin// Add/erase ranges on \mathbb{Z}// Reference: <https://satanic0258.github.io/snippets/data-structure/SegmentMap.html> (Almost transcribed from this code)template <typename Int>struct integer_segments {const Int INVALID = -1;std::map<Int, Int> mp;integer_segments() = default;// Get the range [l, r] that satisfies l <= x <= r, or [INVALID, INVALID] otherwisestd::pair<Int, Int> get(Int x) const {auto itr = mp.upper_bound(x);if (itr == mp.begin() or (--itr)->second < x) {return std::make_pair(INVALID, INVALID);}return *itr;}// Add {l, l + 1, ..., r} and return the merged segment which [l, r] belongs tostd::pair<Int, Int> insert(Int l, Int r) {auto itl = mp.upper_bound(l), itr = mp.upper_bound(r + 1);if (itl != mp.begin() and (--itl)->second < l - 1) {++itl;}if (itl != itr) {l = std::min(l, itl->first), r = std::max(r, std::prev(itr)->second);mp.erase(itl, itr);}mp[l] = r;return std::make_pair(l, r);}// Remove {l, l + 1, ..., r}void remove(Int l, Int r) {auto itl = mp.upper_bound(l), itr = mp.upper_bound(r);if (itl != mp.begin() and (--itl)->second < l) {++itl;}if (itl == itr) {return;}Int tl = std::min(l, itl->first), tr = std::max(r, std::prev(itr)->second);mp.erase(itl, itr);if (tl < l) {mp[tl] = l - 1;}if (r < tr) {mp[r + 1] = tr;}}};#include <iostream>#include <set>using namespace std;int main(){cin.tie(nullptr), ios::sync_with_stdio(false);long long D;int Q;cin >> D >> Q;integer_segments<long long> seg;long long ret = 0;while (Q--) {long long a, b;cin >> a >> b;auto [l, r] = seg.insert(a, b);ret = max(ret, r - l + 1);cout << ret << '\n';}}