結果

問題 No.674 n連勤
コンテスト
ユーザー あ
提出日時 2026-02-17 10:59:50
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 23 ms / 2,000 ms
コード長 2,031 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,840 ms
コンパイル使用メモリ 382,440 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-02-17 10:59:59
合計ジャッジ時間 8,902 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define ALL(a) a.begin(),a.end()
#define rep(i,l,r) for(ll i=l;i<r;i++) //[l,r)
ll inf=4e18;

#include <atcoder/all>
using namespace atcoder;
using mint=modint998244353;
//using mint=modint1000000007;

template<typename T,typename U>
void chmax(T& a,const U& b){a=max(a,b);}
template<typename T,typename U>
void chmin(T& a,const U& b){a=min(a,b);}
void printd(ld x){cout<<fixed<<setprecision(16)<<x<<endl;}
void yesno(bool state){if(state) cout<<"Yes\n";else cout<<"No\n";}

ll isqrt(ll x)
{
  ll ac=0,wa=inf;
  while(wa-ac>1)
  {
    ll wj=(ac+wa)/2;
    if(wj<=x/wj) ac=wj;
    else wa=wj;
  }
  return ac;
}

ll ipow(ll x,ll n)
{
  ll res=1;
  while(n)
  {
    if(n&1) res*=x;
    x*=x;
    n>>=1;
  }
  return res;
}

ll modulo(ll a,ll b){return ((a%b)+b)%b;}

struct interval_set
{
  set<P> st;
  ll len=0;
  ll mx=0;

  void add(ll l,ll r)
  {
    if(l>=r) return;

    auto it=st.lower_bound({l,-inf});
    if(it!=st.begin())
    {
      it--;
      if(it->second<l) it++;
    }

    while(it!=st.end()&&it->first<=r)
    {
      auto [x,y]=*it;
      chmin(l,x);
      chmax(r,y);
      len-=y-x;
      it=st.erase(it);
    }

    st.insert({l,r});
    len+=r-l;
    chmax(mx,r-l);
  }

  void del(ll l,ll r)
  {
    if(l>=r) return;

    auto it=st.lower_bound({l,-inf});
    if(it!=st.begin())
    {
      it--;
      if(it->second<=l) it++;
    }

    while(it!=st.end()&&it->first<r)
    {
      auto [nl,nr]=*it;

      len-=nr-nl;
      it=st.erase(it);

      if(nl<l)
      {
        st.insert({nl,l});
        len+=l-nl;
      }

      if(r<nr)
      {
        st.insert({r,nr});
        len+=nr-r;
      }
    }
  }

  ll size(){return len;};
};

void solve()
{
  ll n,q;
  cin>>n>>q;

  interval_set is;
  rep(_,0,q)
  {
    ll l,r;
    cin>>l>>r;
    r++;
    is.add(l,r);
    cout<<is.mx<<'\n';
  }
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll t=1;
  rep(_,0,t) solve();
}
0