結果
問題 | No.674 n連勤 |
ユーザー | raven7959 |
提出日時 | 2022-03-09 17:25:15 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 63 ms / 2,000 ms |
コード長 | 5,948 bytes |
コンパイル時間 | 2,300 ms |
コンパイル使用メモリ | 208,528 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-13 17:12:44 |
合計ジャッジ時間 | 4,269 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 1 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 7 ms
5,376 KB |
testcase_12 | AC | 7 ms
5,376 KB |
testcase_13 | AC | 51 ms
5,376 KB |
testcase_14 | AC | 53 ms
5,376 KB |
testcase_15 | AC | 49 ms
5,376 KB |
testcase_16 | AC | 63 ms
5,376 KB |
testcase_17 | AC | 63 ms
5,376 KB |
testcase_18 | AC | 57 ms
5,376 KB |
testcase_19 | AC | 50 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--) #define all(x) (x).begin(), (x).end() #define sz(x) int(x.size()) #define yn(joken) cout<<((joken) ? "Yes" : "No")<<endl #define YN(joken) cout<<((joken) ? "YES" : "NO")<<endl using namespace std; using ll = long long; using vi = vector<int>; using vl = vector<ll>; using vs = vector<string>; using vc = vector<char>; using vd = vector<double>; using vvi = vector<vector<int>>; using vvl = vector<vector<ll>>; using vvd = vector<vector<double>>; using vvvl = vector<vector<vector<ll>>>; const int INF = 1e9; const ll LINF = 1e18; 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 (b < a) { a = b; return 1; } return 0; } template <class T> vector<T> make_vec(size_t a) { return vector<T>(a); } template <class T, class... Ts> auto make_vec(size_t a, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...)); } template <typename T> istream& operator>>(istream& is, vector<T>& v) { for (int i = 0; i < int(v.size()); i++) { is >> v[i]; } return is; } template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) { for (int i = 0; i < int(v.size()); i++) { os << v[i]; if (i < int(v.size()) - 1) os << ' '; } return os; } // 区間は閉区間で管理 // bool covered(T x): 点xをカバーされているかどうかを返す // bool covered(T l,T r): 閉区間[l,r]がカバーされているかどうかを返す // pair<T,T> covered_by(T x): 点xをカバーしている区間を返す,存在しない場合は[-TINF,-TINF] // pair<T,T> covered_by(T l,T r): 上のやつの閉区間[l,r]バージョン // T insert(T x): 点xを追加する,区間に含まれる点の数の増加量を返す // T insert(T l,T r): 閉区間[l,r]を追加する,区間に含まれる点の数の増加量を返す // T erase(T x): 点xを削除する,区間に含まれる点の数の減少量を返す // T erase(T l,T r): 閉区間[l,r]を削除する,区間に含まれる点の数の減少量を返す // int size(): 区間の数を返す // T mex(T x=0): x以上の範囲でのmexを返す // T len(): 区間の長さの合計を返す // T points(): 区間に含まれる点の数の合計を返す template<typename T> struct RangeSet{ set<pair<T,T>> st; T TINF,num; RangeSet(): num(0) { TINF=numeric_limits<T>::max()/2; st.emplace(TINF,TINF); st.emplace(-TINF,-TINF); } bool covered(T l,T r){ assert(l<=r); auto itr=prev(st.lower_bound({l+1,l+1})); return itr->first<=l and r<=itr->second; } bool covered(T x){ return covered(x,x); } 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 and r<=itr->second) return *itr; return make_pair(-TINF,-TINF); } pair<T,T> covered_by(T x){ return covered_by(x,x); } T insert(T l,T r){ assert(l<=r); auto itr=prev(st.lower_bound({l+1,l+1})); if(itr->first<=l and r<=itr->second) return T(0); T sum_erased=T(0); if(itr->first<=l and l<=itr->second+1){ l=itr->first; sum_erased+=itr->second-itr->first+1; itr=st.erase(itr); } else itr=next(itr); while(r>itr->second){ sum_erased+=itr->second-itr->first+1; itr=st.erase(itr); } if(itr->first-1<=r and r<=itr->second){ sum_erased+=itr->second-itr->first+1; r=itr->second; st.erase(itr); } st.emplace(l,r); num+=r-l+1-sum_erased; return r-l+1-sum_erased; } T insert(T x){ return insert(x,x); } T erase(T l,T r){ assert(l<=r); auto itr=prev(st.lower_bound({l+1,l+1})); if(itr->first<=l and r<=itr->second){ // 完全に1つの区間に包含されている if(itr->first<l) st.emplace(itr->first,l-1); if(r<itr->second) st.emplace(r+1,itr->second); st.erase(itr); num-=r-l+1; return r-l+1; } T ret=T(0); if(itr->first<=l and 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); while(itr->second<=r){ ret+=itr->second-itr->first+1; itr=st.erase(itr); } // 右端が区間の間にあるか if(itr->first<=r and r<=itr->second){ ret+=r-itr->first+1; if(r<itr->second) st.emplace(r+1,itr->second); st.erase(itr); } num-=ret; return ret; } T erase(T x){ return erase(x,x); } int size(){ return (int)st.size()-2; } T mex(T x=0){ auto itr=prev(st.lower_bound({x+1,x+1})); if(itr->first<=x and x<=itr->second) return itr->second+1; else return x; } T len(){ return num-size(); } T points(){ return num; } // for debug void output(){ cout<<"RangeSet : "; for(auto &p:st){ if(p.first==-TINF or p.second==TINF) continue; cout<<"["<<p.first<<", "<<p.second<<"] "; } cout<<"\n"; } }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); ll D,Q; cin>>D>>Q; RangeSet<ll> RS; ll ans=0; while(Q--){ ll A,B; cin>>A>>B; RS.insert(A,B); auto ret=RS.covered_by(A); chmax(ans,ret.second-ret.first+1); cout<<ans<<endl; } }