結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
コンテスト
ユーザー wu-mingxuan
提出日時 2026-10-20 23:26:13
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 4,072 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,203 ms
コンパイル使用メモリ 365,460 KB
実行使用メモリ 1,310,080 KB
最終ジャッジ日時 2026-10-20 23:26:43
合計ジャッジ時間 19,996 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge6_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 4 MLE * 2 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e18+9;
const int MAXN=2400010;
int x[150010],lt[150010],rt[150010];
int u[300010],v[600010],len[600010],p[MAXN],ans[600010];
void build(int rt,int l,int r)
{
    if(l==r)p[rt]=len[l];
    else
    {
        int mid=(l+r)/2;
        build(rt*2,l,mid);
        build(rt*2+1,mid+1,r);
        p[rt]=p[rt*2]+p[rt*2+1];
    }
}
struct node{
    int val[MAXN],lazy1[MAXN];
    bool lazy0[MAXN];
    void push_up(int rt)
    {
        val[rt]=val[rt*2]+val[rt*2+1];
    }
    void push_down1(int rt)
    {
        if(lazy1[rt]!=0)
        {
            val[rt*2]+=lazy1[rt]*p[rt*2];
            val[rt*2+1]+=lazy1[rt]*p[rt*2+1];
            lazy1[rt*2]+=lazy1[rt];
            lazy1[rt*2+1]+=lazy1[rt];
            lazy1[rt]=0;
        }
    }
    void push_down0(int rt)
    {
        if(lazy0[rt])
        {
            val[rt*2]=val[rt*2+1]=0;
            lazy0[rt*2]=lazy0[rt*2+1]=1;
            lazy0[rt]=0;
        }
    }
    void update1(int rt,int l,int r,int ul,int ur)
    {
        if(ul>r||ur<l)return;
        push_down0(rt);
        if(ul<=l&&ur>=r)
        {
            val[rt]+=p[rt];
            ++lazy1[rt];
            return;
        }
        push_down1(rt);
        int mid=(l+r)/2;
        update1(rt*2,l,mid,ul,ur);
        update1(rt*2+1,mid+1,r,ul,ur);
        push_up(rt);
    }
    void update0(int rt,int l,int r,int ul,int ur)
    {
        if(ul>r||ur<l)return;
        push_down1(rt);
        if(ul<=l&&ur>=r)
        {
            val[rt]=0;
            lazy0[rt]=1;
            lazy1[rt]=0;
            return;
        }
        push_down0(rt);
        int mid=(l+r)/2;
        update0(rt*2,l,mid,ul,ur);
        update0(rt*2+1,mid+1,r,ul,ur);
        push_up(rt);
    }
    int query(int rt,int l,int r,int ql,int qr)
    {
        if(ql>r||qr<l)return 0;
        if(ql<=l&&qr>=r)return val[rt];
        push_down1(rt);
        push_down0(rt);
        int mid=(l+r)/2,ans;
        ans=query(rt*2,l,mid,ql,qr)+query(rt*2+1,mid+1,r,ql,qr);
        return ans;
    }
}tr[5];
signed main()
{
//    freopen("color.in","r",stdin);
//    freopen("color.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,q,k=0;
    int L,R,mid;
    int a,b,c,d,e,mx,cnt,col;
    cin>>n>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>x[i]>>lt[i]>>rt[i];
        u[i*2-1]=lt[i];
        u[i*2]=rt[i];
    }
    sort(u+1,u+q*2+1);
    for(int i=1;i<=q*2;i++)
    {
        if(i==1)
        {
            v[++k]=u[1],len[k]=1;
            continue;
        }
        if(i!=1&&u[i]==u[i-1])continue;
        if(u[i]-u[i-1]==1)
        {
            v[++k]=u[i],len[k]=1;
        }
        else
        {
            v[++k]=u[i-1]+1,len[k]=u[i]-u[i-1]-1;
            v[++k]=u[i],len[k]=1;
        }
    }
    build(1,1,k);
    for(int i=1;i<=q;i++)
    {
        L=1,R=k;
        while(L<=R)
        {
            mid=(L+R)/2;
            if(v[mid]<lt[i])L=mid+1;
            else R=mid-1;
        }
        lt[i]=L;
        L=1,R=k;
        while(L<=R)
        {
            mid=(L+R)/2;
            if(v[mid]<rt[i])L=mid+1;
            else R=mid-1;
        }
        rt[i]=L;
        if(x[i]==0)
        {
            a=tr[0].query(1,1,k,lt[i],rt[i]);
            b=tr[1].query(1,1,k,lt[i],rt[i]);
            c=tr[2].query(1,1,k,lt[i],rt[i]);
            d=tr[3].query(1,1,k,lt[i],rt[i]);
            e=tr[4].query(1,1,k,lt[i],rt[i]);
            mx=max(a,max(max(b,c),max(d,e)));
            cnt=0;
            if(a==mx)++cnt,col=1;
            if(b==mx)++cnt,col=2;
            if(c==mx)++cnt,col=3;
            if(d==mx)++cnt,col=4;
            if(e==mx)++cnt,col=5;
            if(cnt==1)ans[col]+=mx;
        }
        else
        {
            for(int j=1;j<=5;j++)
            {
                if(j==x[i])tr[j-1].update1(1,1,k,lt[i],rt[i]);
                else tr[j-1].update0(1,1,k,lt[i],rt[i]);
            }
        }
    }
    for(int i=1;i<=5;i++)
    {
        ans[i]+=tr[i-1].val[1];
        cout<<ans[i]<<" ";
    }
    return 0;
}
0