結果
問題 | No.674 n連勤 |
ユーザー |
![]() |
提出日時 | 2021-02-14 01:57:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 3,563 bytes |
コンパイル時間 | 1,591 ms |
コンパイル使用メモリ | 82,600 KB |
最終ジャッジ日時 | 2025-01-18 20:16:10 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:144:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 144 | scanf("%lld%d", &d, &q); | ~~~~~^~~~~~~~~~~~~~~~~~ main.cpp:147:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 147 | scanf("%lld%lld", &a, &b); | ~~~~~^~~~~~~~~~~~~~~~~~~~
ソースコード
#include <cassert>#include <iostream>#include <limits>#include <set>#include <vector>template <class T>struct RangeSet {private:const T TINF = std::numeric_limits<T>::max() / 2;std::set<std::pair<T, T>> st;public:RangeSet() {st.emplace(-TINF, -TINF + 1);st.emplace(TINF, TINF + 1);}//[l, r) is covered?bool covered(const T l, const T r) {assert(l < r);auto itr = prev(st.lower_bound({l + 1, -TINF}));return itr->first <= l and r <= itr->second;}//[x, x + 1) is covered?bool covered(const T x) { return covered(x, x + 1); }//return section which covers[l, r)//if not exists, return[-TINF, -TINF)std::pair<T, T> covered_by(const T l, const T r) {assert(l < r);auto itr = prev(st.lower_bound({l + 1, -TINF}));if(itr->first <= l and r <= itr->second) return *itr;return {-TINF, -TINF};}//return section which covers[x, x + 1)//if not exists, return[-TINF, -TINF)std::pair<T, T> covered_by(const T x) { return covered_by(x, x + 1); }//insert[l, r), and return incrementT insert(T l, T r) {if(l >= r) return 0;auto itr = prev(st.lower_bound({l + 1, -TINF}));if(itr->first <= l and r <= itr->second) return T(0);T sum_erased = T(0);if(itr->first <= l and l <= itr->second) {l = itr->first;sum_erased += itr->second - itr->first;itr = st.erase(itr);} elseitr = next(itr);while(r > itr->second) {sum_erased += itr->second - itr->first;itr = st.erase(itr);}if(itr->first <= r) {sum_erased += itr->second - itr->first;r = itr->second;st.erase(itr);}st.emplace(l, r);return r - l - sum_erased;}//insert[x, x + 1), and return incrementT insert(const T x) { return insert(x, x + 1); }// erase [l, r), and return decrementT erase(const T l, const T r) {assert(l < r);auto itr = prev(st.lower_bound({l + 1, -TINF}));if(itr->first <= l and r <= itr->second) {if(itr->first < l) st.emplace(itr->first, l);if(r < itr->second) st.emplace(r, itr->second);st.erase(itr);return r - l;}T ret = T(0);if(itr->first <= l and l < itr->second) {ret += itr->second - l;if(itr->first < l) st.emplace(itr->first, l);itr = st.erase(itr);} elseitr = next(itr);while(itr->second <= r) {ret += itr->second - itr->first;itr = st.erase(itr);}if(itr->first < r) {ret += r - itr->first;st.emplace(r, itr->second);st.erase(itr);}return ret;}// erase [x, x + 1), and return decrementT erase(const T x) { return erase(x, x + 1); }int size() { return (int)st.size() - 2; }int mex(const T x = 0) {auto itr = prev(st.lower_bound({x + 1, -TINF}));if(itr->first <= x and x < itr->second)return itr->second;elsereturn x;}T sum_all() const {T res = 0;for(auto &p : st) {if(std::abs(p.first) == TINF) continue;res += p.second - p.first;}return res;}std::set<std::pair<T, T>> get() const {std::set<std::pair<T, T>> res;for(auto &p : st) {if(std::abs(p.first) == TINF) continue;res.emplace(p.first, p.second);}return res;}void dump() const {std::cout << "Rangeset:";for(auto &p : st) {if(std::abs(p.first) == TINF) continue;std::cout << "[" << p.first << "," << p.second << "),";}std::cout << '\n';}};long long a, b, d, res;int q;int main() {scanf("%lld%d", &d, &q);RangeSet<long long> st;while(q--) {scanf("%lld%lld", &a, &b);st.insert(a, b + 1);auto [l, r] = st.covered_by(a);res = std::max(res, r - l);printf("%lld\n", res);}}