結果
問題 | No.674 n連勤 |
ユーザー | Slephy |
提出日時 | 2023-08-19 20:23:17 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 6,336 bytes |
コンパイル時間 | 2,360 ms |
コンパイル使用メモリ | 210,200 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-07 03:18:58 |
合計ジャッジ時間 | 4,163 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 2 ms
5,376 KB |
testcase_12 | AC | 3 ms
5,376 KB |
testcase_13 | AC | 12 ms
5,376 KB |
testcase_14 | AC | 15 ms
5,376 KB |
testcase_15 | AC | 11 ms
5,376 KB |
testcase_16 | AC | 24 ms
5,376 KB |
testcase_17 | AC | 24 ms
5,376 KB |
testcase_18 | AC | 18 ms
5,376 KB |
testcase_19 | AC | 13 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int INF = (int)1e9 + 1001010; constexpr ll llINF = (ll)4e18 + 22000020; const string endn = "\n"; template <class T> inline vector<vector<T>> vector2(size_t i, size_t j, const T &init = T()) {return vector<vector<T>>(i, vector<T>(j, init));} const string ELEM_SEPARATION = " ", VEC_SEPARATION = endn; template<class T> istream& operator >>(istream &i, vector<T> &A) {for(auto &I : A) {i >> I;} return i;} template<class T> ostream& operator <<(ostream &o, const vector<T> &A) {int i=A.size(); for(auto &I : A){o << I << (--i ? ELEM_SEPARATION : "");} return o;} template<class T> ostream& operator <<(ostream &o, const vector<vector<T>> &A) {int i=A.size(); for(auto &I : A){o << I << (--i ? VEC_SEPARATION : "");} return o;} template<class T> vector<T>& operator ++(vector<T> &A, int n) {for(auto &I : A) {I++;} return A;} template<class T> vector<T>& operator --(vector<T> &A, int n) {for(auto &I : A) {I--;} return A;} template<class T, class U> bool chmax(T &a, const U &b) {return ((a < b) ? (a = b, true) : false);} template<class T, class U> bool chmin(T &a, const U &b) {return ((a > b) ? (a = b, true) : false);} ll floor(ll a, ll b) {assert(b != 0); return((a%b != 0 && ((a>0) != (b>0))) ? a/b-1 : a/b);} ll ceil (ll a, ll b) {assert(b != 0); return((a%b != 0 && ((a>0) == (b>0))) ? a/b+1 : a/b);} // ================================== ここまでテンプレ ================================== enum class RangeSetType{ NotMergeAdjacent = 0, // [l, x]と[x, r]を結合しない MergeAdjcent = 1, // [l, x]と[x, r]を結合する }; template<class T> class RangeSet{ const RangeSetType rs_type; const int TYPE; set<pair<T, T>> st; const T INF; public: const pair<T, T> npos; RangeSet(RangeSetType rs_type = RangeSetType::MergeAdjcent) : rs_type(rs_type), TYPE(static_cast<int>(rs_type)), INF(numeric_limits<T>::max()), npos(numeric_limits<T>::max(), numeric_limits<T>::max()){ st.emplace(INF, INF); st.emplace(-INF, -INF); } // 閉区間[l, r]が一つの区間に被覆されているかを返す bool covered(T l, T r){ assert(l <= r); auto itr = prev(st.lower_bound({l+1, l+1})); return (itr->first <= l && r <= itr->second); } bool covered(T x){ return covered(x, x); } // 閉区間[l, r]を被覆するような区間が存在するならばそれを返す。存在しないならばnposを返す。 pair<T, T> covered_by(T l, T r){ assert(l <= r); auto itr = prev(st.lower_bound({l+1, l+1})); if(itr->first <= l && r <= itr->second) return *itr; else return {this->INF, this->INF}; } pair<T, T> covered_by(T x){ return covered_by(x, x); } // 閉区間[l, r]を挿入し、要素の増加量を返す T insert(T l, T r){ assert(l <= r); auto itr = prev(st.lower_bound({l+1, l+1})); // ✅ itr->first <= l T ret = 0; auto update_ret = [&ret](auto itr) -> void {ret -= (itr->second - itr->first + 1);}; if(itr->second >= r){ // *itrに完全に含まれているとき return 0; } else if(itr->second + TYPE >= l){ // *itrと共通部分を持つとき、merge update_ret(itr); l = itr->first; itr = st.erase(itr); } else{ // そうでないとき、skip itr = next(itr); } // ✅ itr->first > l // *itrが[l, r]に完全に包含されるとき while(itr->second <= r){ update_ret(itr); itr = st.erase(itr); } // ✅ itr->first >= l && itr->second > r if(itr->first <= r + TYPE){ update_ret(itr); r = itr->second; st.erase(itr); } st.emplace(l, r); ret += r - l + 1; return ret; } T insert(T x){ return insert(x, x); } // 閉区間[l, r]を削除し、要素の減少量を返す T erase(T l, T r){ assert(l <= r); auto itr = prev(st.lower_bound({l+1, l+1})); // ✅ itr->first <= l // *itrに完全に含まれている if(r <= itr->second){ if(itr->first < l) st.emplace(itr->first, l-1); if(r < itr->second) st.emplace(r+1, itr->second); st.erase(itr); return r-l+1; } T ret = 0; if(l <= itr->second){ ret += itr->second - l + 1; if(itr->first < l) st.emplace(itr->first, l-1); itr = st.erase(itr); } else{ itr = next(itr); } // ✅ itr->first > l while(itr->second <= r){ ret += itr->second - itr->first + 1; itr = st.erase(itr); } if(itr->first <= r){ ret += r - itr->first + 1; if(r < itr->second) st.emplace(r+1, itr->second); st.erase(itr); } return ret; } T erase(T x){ return erase(x, x); } // 格納されている閉区間の個数を返す int size(){ return (int)st.size() - 2; } // x以上の値で、どの区間にも含まれない整数のうち最小の整数を返す T mex(T x = 0){ auto itr = prev(st.lower_bound({x+1, x+1})); if(x <= itr->second) return itr->second + 1; else return x; } // x, yが同じ閉区間に含まれるかを判定する // x, yのいずれかがどの閉区間にも含まれないのであればfalseと判定する bool same(T x, T y){ auto cover_x = covered_by(x); auto cover_y = covered_by(y); if(cover_x == this->npos || cover_y == this->npos) return false; else return (cover_x == cover_y); } }; int main(int argc, char *argv[]){ ios::sync_with_stdio(false); cin.tie(nullptr); ll d, q; cin >> d >> q; RangeSet<ll> rs(RangeSetType::MergeAdjcent); ll ans = 0; for(int i = 0; i < q; i++){ ll a, b; cin >> a >> b; rs.insert(a, b); auto cover = rs.covered_by(a); ll len = cover.second - cover.first + 1; chmax(ans, len); cout << ans << endn; } return 0; }