結果

問題 No.674 n連勤
コンテスト
ユーザー 卢泓希
提出日時 2025-10-22 20:27:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,884 bytes
コンパイル時間 1,869 ms
コンパイル使用メモリ 199,796 KB
実行使用メモリ 178,308 KB
最終ジャッジ日時 2025-10-22 20:27:55
合計ジャッジ時間 7,354 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 RE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define fi first
#define sc second
#define pii pair<int,int>
#define pdd pair<double,double>
#define pb push_back
#define umap unordered_map
#define mset multiset
#define pq priority_queue
#define ull unsigned long long
#define i128 __int128
#define ld long double
#define fixs fixed<<setprecision
#define FileIn(x) freopen(x".in","r",stdin)
#define FileOut(x) freopen(x".out","w",stdout)
#define FileIO(x) FileIn(x),FileOut(x);
const int maxn=1e5+10;
const int inf=2e18;
struct node{
    int l,r,ls,rs;
    i128 lsum,rsum,sum,maxx,tag;
    void cov(i128 x){
        lsum=rsum=sum=x*(r-l+1),tag=x,maxx=max(x,(i128)0)*(r-l+1);
    }
    node operator +(node x){
        node res;
        if(l==-1) return x;
        if(x.l==-1) return (*this);
        res.l=l,res.r=x.r,res.ls=res.rs=-1,res.sum=sum+x.sum,res.tag=inf;
        res.lsum=max(lsum,sum+x.lsum),res.rsum=max(x.rsum,x.sum+rsum);
        res.maxx=max({maxx,x.maxx,rsum+x.lsum});
        return res;
    }
};
bool ir(int L,int R,int l,int r){
    return (L<=l)&&(r<=R);
}
bool ofr(int L,int R,int l,int r){
    return (R<l)||(r<L);
}
struct SGT{
    node tr[maxn<<4];
    int rt,cnt;
    void init(int n){
        rt=cnt=1,tr[rt]={1,n,0,0,(i128)-n*n,(i128)-n*n,(i128)-n*n,0,-n};
    }
    int New(int l,int r){
        tr[++cnt]={l,r,0,0,0,0,0,0,0};
        return cnt;
    }
    void pushup(int u){
        if(!tr[u].ls) return ;
        int Tl=tr[u].ls,Tr=tr[u].rs;
        tr[u]=tr[tr[u].ls]+tr[tr[u].rs];
        tr[u].ls=Tl,tr[u].rs=Tr;
    }
    void pushdown(int u){
        if(!tr[u].ls){
            int mid=(tr[u].l+tr[u].r)>>1;
            tr[u].ls=New(tr[u].l,mid);
        }
        if(!tr[u].rs){
            int mid=(tr[u].l+tr[u].r)>>1;
            tr[u].rs=New(mid+1,tr[u].r);
        }
        int k=tr[u].tag;
        tr[u].tag=inf,tr[tr[u].ls].cov(k),tr[tr[u].rs].cov(k);
    }
    void upd(int u,int l,int r,int k){
        if(tr[u].tag!=inf) pushdown(u);
        if(ir(l,r,tr[u].l,tr[u].r)) tr[u].cov(k);
        else if(!ofr(l,r,tr[u].l,tr[u].r)) upd(tr[u].ls,l,r,k),upd(tr[u].rs,l,r,k),pushup(u);
    }
    node query(int u,int l,int r){
        if(tr[u].tag!=inf) pushdown(u);
        if(ir(l,r,tr[u].l,tr[u].r)) return tr[u];
        else if(!ofr(l,r,tr[u].l,tr[u].r)) return query(tr[u].ls,l,r)+query(tr[u].rs,l,r);
        else return {-1,-1,-1,-1,-1,-1,-1,-1,-1};
    }
}sgt;
int n,q;
void solve(){
    cin>>n>>q,sgt.init(n);
    while(q--){
        int l,r;
        cin>>l>>r,l++,r++,sgt.upd(1,l,r,1);
        cout<<(int)sgt.query(1,1,n).maxx<<endl;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}
/*
Samples
input:

output:

THINGS TODO:
检查freopen，尤其是后缀名
检查空间
检查调试语句是否全部注释
*/
0