結果
問題 | No.674 n連勤 |
ユーザー | karinohito |
提出日時 | 2022-11-11 13:46:15 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 4,373 bytes |
コンパイル時間 | 2,271 ms |
コンパイル使用メモリ | 209,440 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-13 09:35:39 |
合計ジャッジ時間 | 4,047 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 6 ms
6,944 KB |
testcase_12 | AC | 6 ms
6,940 KB |
testcase_13 | AC | 47 ms
6,940 KB |
testcase_14 | AC | 52 ms
6,940 KB |
testcase_15 | AC | 50 ms
6,940 KB |
testcase_16 | AC | 65 ms
6,944 KB |
testcase_17 | AC | 64 ms
6,940 KB |
testcase_18 | AC | 58 ms
6,944 KB |
testcase_19 | AC | 49 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; //#include <atcoder/all> //using namespace atcoder; using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; using vvvvll = vector<vvvll>; using vvvvvll = vector<vvvvll>; using vvvvvvll = vector<vvvvvll>; using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>; using vvvvb = vector<vvvb>; using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>; using vvvvd = vector<vvvd>; using vvvvvd = vector<vvvvd>; #define all(A) A.begin(),A.end() #define ALL(A) A.begin(),A.end() #define rep(i, n) for (ll i = 0; i < (ll) (n); i++) using pqr = priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>; #define tN(t) (t==1?XN:YN) #define tS(t) (t==1?XS:YS) #define tA(t) (t==1?XA:YA) template<class T> bool chmax(T& p, T q, bool C = 1) { if (C == 0 && p == q) { return 1; } if (p < q) { p = q; return 1; } else { return 0; } } template<class T> bool chmin(T& p, T q, bool C = 1) { if (C == 0 && p == q) { return 1; } if (p > q) { p = q; return 1; } else { return 0; } } ll gcd(ll(a), ll(b)) { if (b == 0)return a; ll c = a; while (a % b != 0) { c = a % b; a = b; b = c; } return b; } ll sqrtz(ll N) { ll L = 0; ll R = sqrt(N) + 10000; while (abs(R - L) > 1) { ll mid = (R + L) / 2; if (mid * mid <= N)L = mid; else R = mid; } return L; } /* 区間をsetで管理するテク 区間は半開区間で持たせる[L,R) */ template<class T> struct rangeset{ set<pair<T,T>> S; T INF; rangeset(){ INF=2e18;; S.insert({INF,INF}); S.insert({-INF,-INF}); } bool iscovered(T L,T R){ //assert(L<=R); auto itr=S.lower_bound({L+1,L+1}); itr=prev(itr); auto st=*itr; return (itr->first<=L&&R<=itr->second); } bool iscovered(T x){ return iscovered(x,x+1); } pair<T,T> covered(T L,T R){ //assert(L<=R); auto itr=S.lower_bound({L+1,L+1}); itr--; auto st=*itr; if(itr->first<=L&&R<=itr->second){ return st; } else{ return {INF,INF}; } } pair<T,T> covered(T x){ return covered(x,x+1); } T insert(T L,T R){ if(iscovered(L,R))return T(0); auto itr=S.lower_bound({L+1,L+1}); itr=prev(itr); T res=T(0); auto st=*itr; if(itr->first<=L&&L<=itr->second){ L=st.first; res-=itr->second-itr->first; itr=S.erase(itr); } else itr=next(itr); while(R>itr->second){ res-=itr->second-itr->first; itr=S.erase(itr); } if(itr->first<=R&&R<=itr->second){ res-=itr->second-itr->first; R=itr->second; itr=S.erase(itr); } S.insert({L,R}); res+=R-L; return res; } T insert(T x){ return insert(x,x+1); } T erase(T L,T R){ auto itr=S.lower_bound({L+1,L+1}); itr=prev(itr); T res=T(0); auto st=*itr; if(itr->first<=L&&R<=itr->second){ if(itr->first<L)S.insert({itr->first,L}); if(R<itr->second)S.insert({R,itr->second}); S.erase(itr); return R-L; } if(itr->first<=L&&L<itr->second){ res+=itr->second-L; if(itr->first<L)S.insert({itr->first,L}); itr=S.erase(itr); } else itr=next(itr); while(itr->second<=R){ res+=itr->second-itr->first; itr=S.erase(itr); } if(itr->first<R&&R<=itr->second){ res+=R-itr->first; if(R<itr->second)S.insert({R,itr->second}); S.erase(itr); } return res; } T erase(T x){ return erase(x,x+1); } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); rangeset<ll> S; ll N,Q; cin>>N>>Q; ll an=0; rep(i,Q){ ll A,B; cin>>A>>B; S.insert(A,B+1); auto p=S.covered(A); chmax(an,p.second-p.first); cout<<an<<endl; } }