結果

問題 No.674 n連勤
コンテスト
ユーザー kiyoshi0205
提出日時 2021-01-12 11:39:36
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,213 bytes
コンパイル時間 746 ms
コンパイル使用メモリ 72,260 KB
最終ジャッジ日時 2024-11-14 23:58:07
合計ジャッジ時間 1,641 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:20:16: error: 'numeric_limits' was not declared in this scope
   20 |   const T TINF=numeric_limits<T>::max()/2;
      |                ^~~~~~~~~~~~~~
main.cpp:20:32: error: expected primary-expression before '>' token
   20 |   const T TINF=numeric_limits<T>::max()/2;
      |                                ^
main.cpp:20:38: error: no matching function for call to 'max()'
   20 |   const T TINF=numeric_limits<T>::max()/2;
      |                                 ~~~~~^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/string:50,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/locale_classes.h:40,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/ios_base.h:41,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ios:42,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:38,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/iostream:39,
                 from main.cpp:4:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
main.cpp:20:38: note:   candidate expects 2 arguments, 0 provided
   20 |   const T TINF=numeric_limits<T>::max()/2;
      |                                 ~~~~~^~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/home/linuxbrew/.linuxbrew/Cellar/

ソースコード

diff # 

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
using ll=long long;
void startupcpp(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}

// Merge:0->interval set,1->point set
template<typename T,int Merge=1>
struct rangeset:set<pair<T,T>>{
private:
  using P=pair<T,T>;
  using seitr=_Rb_tree_const_iterator<P>;
  const T TINF=numeric_limits<T>::max()/2;
public:
  // There are all [L,R] (not [L,R) )
  rangeset(){
    this->emplace(-TINF,-TINF);
    this->emplace(TINF,TINF);
  }

  // [L,R] covered?
  bool covered(T L,T R){
    // assert(L<=R);
    seitr itr(--this->lower_bound(P(L+1,L)));
    return R<=itr->second;
  }
  bool covered(T x){
    return covered(x,x);
  }

  // what is covered [L,R] (not cover->return [-TINF,-TINF])
  P covered_by(T L,T R){
    // assert(L<=R);
    seitr itr(--this->lower_bound(P(L+1,L)));
    if(R<=itr->second)return *itr;
    else return *(this->begin());
  }
  P covered_by(T x){
    return covered_by(x,x);
  }
  //insert [L,R] and merge, return (how many add point or interval)
  pair<seitr,T> insert(T L,T R){
    // assert(L<=R);
    seitr itr(--this->lower_bound(P(L+1,L)));
    if(R<=itr->second)return pair<seitr,T>(itr,0);

    T deletecnt(0);
    if(itr->second<L-Merge){
      ++itr;
    }else{
      L=itr->first;
      deletecnt=itr->second-itr->first+Merge;
      itr=this->erase(itr);
    }
    while(itr->second<=R){
      deletecnt+=itr->second-itr->first+Merge;
      itr=this->erase(itr);
    }
    if(itr->first<=R+Merge){
      R=itr->second;
      deletecnt+=itr->second-itr->first+Merge;
      itr=this->erase(itr);
    }
    itr=this->emplace_hint(itr,L,R);
    return pair<seitr,T>(itr,R-L+Merge-deletecnt);
  }
  pair<seitr,T> insert(T x){
    // assert(Merge==1);
    return insert(x,x);
  }
  //delete intersect [L,R], return (how many erase point or interval)
  T remove(T L,T R){
    // assert(L<=R);
    seitr itr(--this->lower_bound(P(L+1,L)));
    if(R<=itr->second){
      if(itr->first!=L)this->emplace_hint(itr,itr->first,L-Merge);
      if(itr->second!=R)this->emplace_hint(next(itr),R+Merge,itr->second);
      this->erase(itr);
      return R-L+Merge;
    }
    T deletecnt(0);
    if(itr->second<=L-Merge){
      ++itr;
    }else{
      deletecnt=itr->second-L+Merge;
      this->emplace_hint(itr,itr->first,L-Merge);
      itr=this->erase(itr);
    }
    while(itr->second<=R){
      deletecnt+=itr->second-itr->first+Merge;
      itr=this->erase(itr);
    }
    if(itr->first<R+Merge){
      deletecnt+=R-itr->first+Merge;
      this->emplace_hint(next(itr),R+Merge,itr->second);
      this->erase(itr);
    }
    return deletecnt;
  }
  T remove(T x){
    // assert(Merge==1);
    return remove(x,x);
  }
  T mex(T x){
    // assert(Merge==1);
    seitr itr(this->lower_bound(P(x,x)));
    if(itr->first<=x)return itr->second+1;
    else return x+1;
  }
};
ll ans;
int main(){
  scanf("%lld");
  int N;
  scanf("%d",&N);
  rangeset<ll> se;
  for(int i=0;i<N;++i){
    ll L,R;
    scanf("%lld %lld",&L,&R);
    auto itr=*se.insert(L,R).first;
    ans=max(ans,itr.second-itr.first+1);
    printf("%lld\n",ans);
  }
}
0