結果
問題 |
No.674 n連勤
|
ユーザー |
![]() |
提出日時 | 2025-04-08 10:22:44 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 23 ms / 2,000 ms |
コード長 | 7,504 bytes |
コンパイル時間 | 2,358 ms |
コンパイル使用メモリ | 212,352 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-04-08 10:22:49 |
合計ジャッジ時間 | 4,209 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#pragma region header #include<algorithm> // ソート, 二分探索, 最大・最小 #include<array> // 固定長配列(C++11~) #include<bitset> // ビット演算・フラグ管理 #include<cassert> // デバッグ用の assert #include<chrono> // 時間計測(C++11~) #include<cinttypes> // int64_t, PRIu64 などのフォーマット指定 #include<climits> // INT_MAX, INT_MIN など #include<cmath> // sqrt, pow, sin, cos など #include<complex> // FFT(高速フーリエ変換)など #include<cstdio> // printf, scanf(Cスタイル) #include<cstring> // memset, memcpy #include<deque> // 両端キュー(deque) #include<functional> // 比較関数 (greater, less) #include<iomanip> // 小数点表示の調整(setprecision など) #include<iostream> // 標準入出力 #include<iterator> // イテレータ操作 #include<limits> // numeric_limits #include<map> // std::map(連想配列) #include<numeric> // gcd, lcm, accumulate など #include<queue> // 優先度付きキュー (priority_queue) #include<random> // 乱数生成(乱択アルゴリズムなど) #include<set> // std::set(集合) #include<sstream> // 文字列ストリーム(stringstream) #include<stack> // スタック(LIFO) #include<string> // 文字列操作 #include<tuple> // tuple, tie #include<type_traits> // 型特性(C++11~) #include<unordered_map> // ハッシュマップ(unordered_map) #include<unordered_set> // ハッシュセット(unordered_set) #include<utility> // pair, swap, move など #include<vector> // 動的配列(最重要) using namespace std; struct Init{Init(){std::cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(20) << fixed;}}init; using ll = long long; using ull = unsigned long long; using ld = long double; #define all(x) begin((x)), end((x)) #define pb push_back #define mp make_pair #define mt make_tuple #define uq(v) v.erase(unique(begin(v), end(v)), end(v)) #define _overload4(_1,_2,_3,_4,name,...) name #define _overload3(_1,_2,_3,name,...) name #define _rep1(n) for(int i=0;i<n;++i) #define _rep2(i,n) for(int i=0;i<n;++i) #define _rep3(i,a,b) for(int i=a;i<b;++i) #define _rep4(i,a,b,c) for(int i=a;i<b;i+=c) #define rep(...) _overload4(__VA_ARGS__,_rep4,_rep3,_rep2,_rep1)(__VA_ARGS__) #define _rrep1(n) for(int i=(n)-1;i>=0;i--) #define _rrep2(i,n) for(int i=(n)-1;i>=0;i--) #define _rrep3(i,a,b) for(int i=(b)-1;i>=(a);i--) #define _rrep4(i,a,b,c) for(int i=a+(b-a-1)/c*c;i>=a;i-=c) #define rrep(...) _overload4(__VA_ARGS__,_rrep4,_rrep3,_rrep2,_rrep1)(__VA_ARGS__) template<class T> using pq = priority_queue<T>; template<class T> using pq_g = priority_queue<T, vector<T>, greater<T>>; template<class T> bool chmax(T &a, const T &b){if(a < b){a = b; return 1; } return 0;} template<class T> bool chmin(T &a, const T &b){if(a > b){a = b; return 1; } return 0;} template<class T> auto min(const T& a){ return *min_element(all(a)); } template<class T> auto max(const T& a){ return *max_element(all(a)); } constexpr ull INF = (1ULL << 61) + (1ULL << 30); constexpr int inf = (1 << 30); constexpr ld EPS = 1e-9; constexpr ld PI = std::acos(ld(-1)); constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}; constexpr int dy[] = {0, 1 ,0, -1, 1, -1, 1, -1}; #pragma endregion header template<typename T> struct RangeSet{ set<pair<T, T>> st; T TINF; RangeSet(){ TINF = numeric_limits<T>::max()/2; st.emplace(TINF, TINF); st.emplace(-TINF, -TINF); } // [l,r] がカバーされているか? bool covered(T l,T r){ assert(l <= r); auto ite = prev(st.lower_bound({l + 1, l + 1})); return (ite->first <= l && r <= ite->second); } // x をカバーしているか? bool covered(T x){ return covered(x, x); } // [l, r]がカバーされているなら,その区間を返す. されていないなら[-TINF,-TINF]を返す pair<T, T> covered_by(T l, T r){ assert(l <= r); auto ite = prev(st.lower_bound({l + 1, l + 1})); if(ite->first <= l && r <= ite->second) return *ite; return make_pair(-TINF, -TINF); } // x がカバーされているなら,その区間を返す. されていないなら[-TINF,-TINF]を返す pair<T, T> covered_by(T x){ return covered_by(x, x); } // [l,r] をカバーする.その時のカバーされた要素の個数を返す. T insert(T l, T r){ assert(l <= r); auto ite = prev(st.lower_bound({l + 1, l + 1})); if(ite->first <= l && r <= ite->second) return T(0); T sum_erased = T(0); if(ite->first <= l && l <= ite->second + 1){ l = ite->first; sum_erased += ite->second - ite->first + 1; ite = st.erase(ite); }else ite = next(ite); while(r > ite->second){ sum_erased += ite->second - ite->first + 1; ite = st.erase(ite); } if(ite->first - 1 <= r && r <= ite->second){ sum_erased += ite->second - ite->first + 1; r = ite->second; st.erase(ite); } st.emplace(l, r); return r - l + 1 - sum_erased; } // x をカバーする.その時のカバーされた要素の個数を返す. T insert(T x){ return insert(x, x); } // [l,r] を消去する.その時の消去された要素の個数を返す. T erase(T l, T r){ assert(l <= r); auto ite = prev(st.lower_bound({l + 1, l + 1})); if(ite->first <= l && r <= ite->second){ if(ite->first < l) st.emplace(ite->first, l - 1); if(r < ite->second) st.emplace(r + 1, ite->second); st.erase(ite); return r - l + 1; } T ret=T(0); if(ite->first <= l && l <= ite->second){ ret += ite->second - l + 1; if(ite->first < l) st.emplace(ite->first, l - 1); ite = st.erase(ite); }else ite = next(ite); while(ite->second <= r){ ret += ite->second - ite->first + 1; ite = st.erase(ite); } if(ite->first <= r && r <= ite->second){ ret += r - ite->first + 1; if(r < ite->second) st.emplace(r + 1, ite->second); st.erase(ite); } return ret; } // x を消去する.その時の消去された要素の個数を返す. T erase(T x){ return erase(x, x); } // 区間の個数を出力 int size(){ return (int)st.size() - 2; } // [x,~) の mex を出力 int mex(T x = 0){ auto ite = prev(st.lower_bound({x + 1, x + 1})); if(ite->first <= x && x <= ite->second) return ite->second + 1; else return x; } // デバッグ void output(){ cout<<"RangeSet : "; for(auto &p : st){ if(p.first == -TINF || p.second == TINF) continue; cout << "[" << p.first << ", " << p.second << "] "; } cout<<"\n"; } }; int main(){ long long D; cin >> D; int Q; cin >> Q; RangeSet<long long> rs; long long mx = 0; for(int i = 0; i < Q; ++i){ long long A, B; cin >> A >> B; rs.insert(A, B); auto [C, D] = rs.covered_by(A, B); mx = max(mx, D - C + 1); cout << mx << "\n"; } }