結果
問題 | No.674 n連勤 |
ユーザー | cureskol |
提出日時 | 2021-10-21 12:30:26 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 1,500 bytes |
コンパイル時間 | 2,679 ms |
コンパイル使用メモリ | 221,656 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-21 07:38:01 |
合計ジャッジ時間 | 3,433 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 1 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 3 ms
6,944 KB |
testcase_12 | AC | 3 ms
6,940 KB |
testcase_13 | AC | 14 ms
6,940 KB |
testcase_14 | AC | 14 ms
6,944 KB |
testcase_15 | AC | 13 ms
6,940 KB |
testcase_16 | AC | 22 ms
6,944 KB |
testcase_17 | AC | 22 ms
6,940 KB |
testcase_18 | AC | 18 ms
6,940 KB |
testcase_19 | AC | 14 ms
6,944 KB |
ソースコード
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define RREP(i,n) for(int i=(n-1);i>=0;i--) #define ALL(v) v.begin(),v.end() using ll=long long; struct SegmentMap{ map<ll,ll> mp;//mp[l]=r:[l,r) //[l,m) [m,r) は[l,r)になる 連続する黒の区間を持つみたいなイメージ const ll LINF=4e18; SegmentMap(){ mp[-LINF]=-LINF; mp[LINF]=LINF; } inline auto get_it(ll a){//aを含む[l,r)のiterator auto it=--mp.upper_bound(a); if(a<(it->second))return it; return mp.end(); } tuple<ll,ll> get(ll a){ auto it=get_it(a); if(it==mp.end())return {LINF,-LINF}; return {it->first,it->second}; } bool same(ll a,ll b){ auto it=get_it(a); return it!=mp.end() && (it->first)<=b && b<(it->second); } tuple<ll,ll> insert(ll l,ll r){//[l,r)を挿入 auto it=--mp.upper_bound(l); if((it->second)>=l)l=it->first; else ++it; while((it->first)<=r){ r=max(r,it->second); it=mp.erase(it); } mp[l]=r; return {l,r}; } void remove(ll l,ll r){//[l,r)と共通部分を持つ区間全削除 auto it=--mp.upper_bound(l); if((it->second)<=l)++it; while((it->first)<r)it=mp.erase(it); } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll d,q;cin>>d>>q; SegmentMap seg; ll ans=0; REP(_,q){ ll a,b;cin>>a>>b; auto [l,r]=seg.insert(a,b+1); ans=max(ans,r-l); cout<<ans<<"\n"; } }