結果

問題 No.674 n連勤
ユーザー mugen_1337mugen_1337
提出日時 2021-01-03 22:05:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 95 ms / 2,000 ms
コード長 4,099 bytes
コンパイル時間 1,905 ms
コンパイル使用メモリ 201,044 KB
最終ジャッジ日時 2025-01-17 09:31:06
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// verification-helper: PROBLEM https://yukicoder.me/problems/1601
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 998244353
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}
//
template<typename T>
struct RangeSet{
set<pair<T,T>> st;
T TINF;
RangeSet(){
TINF=numeric_limits<T>::max()/2;
st.emplace(TINF,TINF);
st.emplace(-TINF,-TINF);
}
// [l,r] covered?
bool covered(T l,T r){
assert(l<=r);
auto ite=prev(st.lower_bound({l+1,l+1}));
return ite->first<=l and r<=ite->second;
}
bool covered(T x){
return covered(x,x);
}
// [l, r]. [-TINF,-TINF]
pair<T,T> covered_by(T l,T r){
assert(l<=r);
auto ite=prev(st.lower_bound({l+1,l+1}));
if(ite->first<=l and r<=ite->second) return *ite;
return make_pair(-TINF,-TINF);
}
pair<T,T> covered_by(T x){
return covered_by(x,x);
}
// insert[l,r],
T insert(T l,T r){
assert(l<=r);
auto ite=prev(st.lower_bound({l+1,l+1}));
if(ite->first<=l and r<=ite->second) return T(0);
T sum_erased=T(0);
if(ite->first<=l and l<=ite->second+1){
l=ite->first;
sum_erased+=ite->second-ite->first+1;
ite=st.erase(ite);
}else ite=next(ite);
while(r>ite->second){
sum_erased+=ite->second-ite->first+1;
ite=st.erase(ite);
}
if(ite->first-1<=r and r<=ite->second){
sum_erased+=ite->second-ite->first+1;
r=ite->second;
st.erase(ite);
}
st.emplace(l,r);
return r-l+1-sum_erased;
}
T insert(T x){
return insert(x,x);
}
// erase [l,r],
T erase(T l,T r){
assert(l<=r);
auto ite=prev(st.lower_bound({l+1,l+1}));
if(ite->first<=l and r<=ite->second){
// 1
if(ite->first<l) st.emplace(ite->first,l-1);
if(r<ite->second) st.emplace(r+1,ite->second);
st.erase(ite);
return r-l+1;
}
T ret=T(0);
if(ite->first<=l and l<=ite->second){
ret+=ite->second-l+1;//
if(ite->first<l) st.emplace(ite->first,l-1);
ite=st.erase(ite);//
}else ite=next(ite);
while(ite->second<=r){
ret+=ite->second-ite->first+1;
ite=st.erase(ite);
}
//
if(ite->first<=r and r<=ite->second){
ret+=r-ite->first+1;
if(r<ite->second) st.emplace(r+1,ite->second);
st.erase(ite);
}
return ret;
}
T erase(T x){
return erase(x,x);
}
// number of range
int size(){
return (int)st.size()-2;
}
// mex [x,~)
int mex(T x=0){
auto ite=prev(st.lower_bound({x+1,x+1}));
if(ite->first<=x and x<=ite->second) return ite->second+1;
else return x;
}
void output(){
cout<<"RangeSet : ";
for(auto &p:st){
if(p.first==-TINF or p.second==TINF) continue;
cout<<"["<<p.first<<", "<<p.second<<"] ";
}
cout<<"\n";
}
};
signed main(){
ll d,q;cin>>d>>q;
RangeSet<ll> st;
ll res=0;
while(q--){
ll l,r;cin>>l>>r;
st.insert(l,r);
auto p=st.covered_by(l);
chmax(res,p.second-p.first+1);
cout<<res<<"\n";
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0