結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー seatofhorse
提出日時 2017-09-03 17:10:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,699 bytes
コンパイル時間 666 ms
コンパイル使用メモリ 69,900 KB
最終ジャッジ日時 2025-01-05 02:37:19
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 RE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>

using ll=long long int;

using P=std::pair<int,int>;

constexpr int MAX_N=(int)1e5;

int n,q;

int diff[MAX_N*2-1],cnt[MAX_N*2-1];

int lazy[MAX_N*2-1];

void init(int _n) {

    n=1;

    while(n<_n)
        n*=2;
}

void eval(int k,int l,int r){

    if(lazy[k]==0)
        return;
    
    if(r-l>1)
        lazy[k*2+1]=lazy[k*2+2]=lazy[k]/2;

    diff[k]=lazy[k];

    cnt[k]=r-l;

    lazy[k]=0;
}

void update(int a,int b,int v,int k,int l,int r) {

    eval(k,l,r);

    if(b<=l||r<=a)
        return;
    
    if(a<=l&&r<=b){
        lazy[k]=v*(r-l);
        eval(k,l,r);
        return;
    }

    update(a,b,v,k*2+1,l,(l+r)/2);
    update(a,b,v,k*2+2,(l+r)/2,r);

    diff[k]=diff[k*2+1]+diff[k*2+2];
    cnt[k]=cnt[k*2+1]+cnt[k*2+2];
}

P operator+ (const P& lhs,const P& rhs){

    return P(lhs.first+rhs.first,lhs.second+rhs.second);
}

P query(int a,int b,int k,int l,int r){

    eval(k,l,r);

    if(b<=l||r<=a)
        return P(0,0);
    
    if(a<=l&&r<=b)
        return P(diff[k],cnt[k]);
    
    return query(a,b,k*2+1,l,(l+r)/2)+query(a,b,k*2+2,(l+r)/2,r);
}

int main() {

    std::cin>>n>>q;

    init(n);

    ll a=0,b=0;

    int x,l,r;

    for(int i=0;i<q;++i){

        std::cin>>x>>l>>r;

        if(x==0){

            P p=query(l,r+1,0,0,n);

            if(p.first>0)
                b+=(p.second+p.first)/2;
            else if(p.first<0)
                a+=(p.second-p.first)/2;
        }
        else if(x==1)
            update(l,r+1,-1,0,0,n);
        else
            update(l,r+1,1,0,0,n);
    }

    P p=query(0,n,0,0,n);

    a+=(p.second-p.first)/2;

    b+=(p.second+p.first)/2;

    std::cout<<a<<' '<<b<<std::endl;

    return 0;
}
0