結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー seatofhorseseatofhorse
提出日時 2017-09-03 17:12:04
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 148 ms / 5,000 ms
コード長 1,698 bytes
コンパイル時間 527 ms
コンパイル使用メモリ 57,048 KB
実行使用メモリ 5,760 KB
最終ジャッジ日時 2024-11-06 20:05:03
合計ジャッジ時間 2,283 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 9 ms
5,248 KB
testcase_07 AC 3 ms
5,248 KB
testcase_08 AC 4 ms
5,248 KB
testcase_09 AC 69 ms
5,248 KB
testcase_10 AC 74 ms
5,248 KB
testcase_11 AC 39 ms
5,248 KB
testcase_12 AC 70 ms
5,248 KB
testcase_13 AC 12 ms
5,248 KB
testcase_14 AC 74 ms
5,248 KB
testcase_15 AC 110 ms
5,248 KB
testcase_16 AC 126 ms
5,248 KB
testcase_17 AC 148 ms
5,760 KB
testcase_18 AC 100 ms
5,760 KB
testcase_19 AC 86 ms
5,632 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>

using ll=long long int;

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

constexpr int MAX_N=(1<<20);

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