結果
問題 |
No.674 n連勤
|
ユーザー |
![]() |
提出日時 | 2025-07-03 09:58:44 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 4,193 bytes |
コンパイル時間 | 3,214 ms |
コンパイル使用メモリ | 285,952 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-07-03 09:58:50 |
合計ジャッジ時間 | 5,093 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; // 書きかけ template<typename T> struct range_set { range_set() { s.emplace(-inf, -inf); s.emplace(inf, inf); } template<typename A, typename D> void insert(T l, T r, const A &add, const D &del) { if (l == r) return; auto it = key(l); if (it->l <= l && r <= it->r) return; if (it->l <= l && l <= it->r) { del(it->l, it->r); l = it->l; it = s.erase(it); } else { it = next(it); } while (it->r < r) { del(it->l, it->r); it = s.erase(it); } if (it->l <= r) { del(it->l, it->r); r = it->r; s.erase(it); } add(l, r); s.emplace(node(l, r)); } void insert(T l, T r) { insert(l, r, [] (T, T) {}, [] (T, T) {}); } template<typename A, typename D> void insert(T k, const A &add, const D &del) { insert(k, k + 1, add, del); } void insert(T k) { insert(k, k + 1); } template<typename A, typename D> void erase(T l, T r, const A &add, const D &del) { if (l == r) return; auto it = key(l); if (it->l <= l && r <= it->r) { if (it->l < l) { add(it->l, l); s.emplace(node(it->l, l)); } if (r < it->r) { add(r, it->r); s.emplace(node(r, it->r)); } del(it->l, it->r); s.erase(it); return; } if (it->l <= l && l < it->r) { if (it->l < l) { add(it->l, l); s.emplace(it->l, l); } del(it->l, it->r); it = s.erase(it); } else { it = next(it); } while (it->r <= r) { del(it->l, it->r); it = s.erase(it); } if (it->l < r) { add(r, it->r); s.emplace(r, it->r); del(it->l, it->r); s.erase(it); } } void erase(T l, T r) { erase(l, r, [] (T, T) {}, [] (T, T) {}); } template<typename A, typename D> void erase(T k, const A &add, const D &del) { erase(k, k + 1, add, del); } void erase(T k) { erase(k, k + 1); } T mex(T k = 0) const { auto it = key(k); return it->l <= k && k < it->r ? it->r : k; } bool covered(T l, T r) const { if (l == r) return true; auto it = key(l); return it->l <= l && r <= it->r; } bool covered(T k) const { return covered(k, k + 1); } pair<T, T> get(T k) const { auto it = key(k); return it->l <= k && k < it->r ? make_pair(it->l, it->r) : make_pair(-inf, -inf); } vector<pair<T, T>> ranges() const { vector<pair<T, T>> res; res.reserve(s.size()); for (auto [l, r] : s) { if (abs(l) != inf && abs(r) != inf) res.emplace_back(l, r); } return res; } void debug() const { for (auto [l, r] : ranges()) { cout << '(' << l << ',' << r << ')'; } cout << endl; } private: static constexpr T inf = numeric_limits<T>::max(); struct node { T l, r; node() : node(-inf, -inf) {} node(T _l, T _r) : l(_l), r(_r) {} constexpr bool operator<(const node &a) const { return l == a.l ? r < a.r : l < a.l; } }; set<node> s; typename set<node>::iterator key(T k) const { return prev(s.upper_bound(node(k, inf))); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); multiset<long long> MS; auto add = [&] (long long l, long long r) -> void { MS.insert(r - l); }; auto del = [&] (long long l, long long r) -> void { MS.erase(MS.find(r - l)); }; long long D; int Q; cin >> D >> Q; range_set<long long> RS; while (Q--) { long long L, R; cin >> L >> R; RS.insert(L, R + 1, add, del); cout << *MS.rbegin() << '\n'; } }