結果
問題 | No.674 n連勤 |
ユーザー | cutmdo |
提出日時 | 2022-09-04 13:07:14 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 2,837 bytes |
コンパイル時間 | 923 ms |
コンパイル使用メモリ | 89,436 KB |
実行使用メモリ | 5,504 KB |
最終ジャッジ日時 | 2024-04-29 12:58:54 |
合計ジャッジ時間 | 2,499 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 8 ms
5,376 KB |
testcase_12 | AC | 9 ms
5,376 KB |
testcase_13 | AC | 71 ms
5,376 KB |
testcase_14 | AC | 75 ms
5,376 KB |
testcase_15 | AC | 73 ms
5,376 KB |
testcase_16 | AC | 100 ms
5,376 KB |
testcase_17 | AC | 103 ms
5,504 KB |
testcase_18 | AC | 88 ms
5,376 KB |
testcase_19 | AC | 77 ms
5,376 KB |
コンパイルメッセージ
main.cpp:23:41: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts' 23 | auto remove(SizeType l, SizeType r, auto& it) { | ^~~~
ソースコード
#include <iostream> #include <iostream> #include <map> #include <stdexcept> #include <deque> template<class ValType = long long, class SizeType = long long> class SegmentMap { const SizeType n; std::map<SizeType, ValType> mp; auto add(SizeType i, ValType val, bool left = true, bool right = true) { auto it = std::prev(mp.upper_bound(i)); if(right && std::next(it)->second == val) { mp.erase(std::next(it)); } if(left && it->second == val) { return; } mp.emplace(i, val); } auto remove(SizeType l, SizeType r, auto& it) { auto nx = std::next(it)->first; auto val = it->second; auto ret = std::next(it); if(l <= it->first) { ret = mp.erase(it); } if(r < nx - 1) { add(r + 1, val, false, true); } return ret; } auto remove(SizeType l, SizeType r) { auto it = std::prev(mp.upper_bound(l)); while(it->first <= r) { it = remove(l, r, it); } } public: SegmentMap(SizeType n) :n(n) { mp.emplace(-1, -1); mp.emplace(0, -2); mp.emplace(n, -1); } auto output() const { for(auto it = std::next(mp.begin()); it != std::prev(mp.end()); ++it) { std::cout << "[" << it->first << ", " << std::next(it)->first - 1 << "] :" << it->second << std::endl; } } auto update(SizeType l, SizeType r, ValType val) { if(l < 0 || r >= n) { throw std::runtime_error(""); } if(l > r) { throw std::runtime_error(""); } remove(l, r); add(l, val); } auto query(SizeType l, SizeType r) { if(l < 0 || r >= n) { throw std::runtime_error(""); } if(l > r) { throw std::runtime_error(""); } auto it = std::prev(mp.upper_bound(l)); std::deque<std::pair<ValType, std::pair<SizeType, SizeType>>> dq; while(it->first <= r) { auto nx = std::next(it)->first; auto nr = std::min(nx - 1, r); auto nl = std::max(l, it->first); dq.emplace_back(it->second, std::pair{nl,nr}); ++it; } return dq; } auto get(SizeType i) { auto it = std::prev(mp.upper_bound(i)); auto nx = std::next(it)->first; auto nr = nx - 1; auto nl = it->first; return std::pair{it->second,std::pair{nl,nr}}; } }; using ll = long long; using std::cout; using std::cin; constexpr char endl = '\n'; signed main() { ll d, q; cin >> d >> q; auto segmap = SegmentMap(d); ll ans = 0; for(int _ = 0; _ < q; ++_) { ll a, b; cin >> a >> b; segmap.update(a, b, 1); auto [__, range] = segmap.get(a); ans = std::max(ans, range.second - range.first + 1); cout << ans << endl; } }