結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー latte0119latte0119
提出日時 2015-10-31 17:33:09
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 122 ms / 5,000 ms
コード長 2,041 bytes
コンパイル時間 454 ms
コンパイル使用メモリ 61,064 KB
実行使用メモリ 6,732 KB
最終ジャッジ日時 2023-10-11 07:15:47
合計ジャッジ時間 3,041 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,732 KB
testcase_01 AC 4 ms
6,608 KB
testcase_02 AC 4 ms
6,620 KB
testcase_03 AC 4 ms
6,488 KB
testcase_04 AC 4 ms
6,652 KB
testcase_05 AC 5 ms
6,604 KB
testcase_06 AC 9 ms
6,540 KB
testcase_07 AC 5 ms
6,568 KB
testcase_08 AC 6 ms
6,612 KB
testcase_09 AC 60 ms
6,520 KB
testcase_10 AC 68 ms
6,648 KB
testcase_11 AC 33 ms
6,652 KB
testcase_12 AC 59 ms
6,568 KB
testcase_13 AC 12 ms
6,544 KB
testcase_14 AC 49 ms
6,616 KB
testcase_15 AC 88 ms
6,572 KB
testcase_16 AC 95 ms
6,568 KB
testcase_17 AC 122 ms
6,524 KB
testcase_18 AC 64 ms
6,604 KB
testcase_19 AC 65 ms
6,664 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#include<cassert>
#include<cstring>
using namespace std;
typedef pair<int,int>pint;
typedef vector<int>vint;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);i++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}


const int SIZE=1<<17;
int datA[SIZE*2-1],datB[SIZE*2-1],lazy[SIZE*2-1];
void init(){
    memset(datA,0,sizeof(datA));
    memset(datB,0,sizeof(datB));
    memset(lazy,0,sizeof(lazy));
}

inline void evaluate(int k,int l,int r){
    if(lazy[k]==1){
        datA[k]=r-l;
        datB[k]=0;
    }
    else if(lazy[k]==2){
        datA[k]=0;
        datB[k]=r-l;
    }
    if(lazy[k]&&k<SIZE-1){
        lazy[k*2+1]=lazy[k];
        lazy[k*2+2]=lazy[k];
    }
    lazy[k]=0;
}

inline void update(int k){
    datA[k]=datA[k*2+1]+datA[k*2+2];
    datB[k]=datB[k*2+1]+datB[k*2+2];
}

void add(int a,int b,int x,int k=0,int l=0,int r=SIZE){
    evaluate(k,l,r);
    if(r<=a||b<=l)return;
    if(a<=l&&r<=b){
        lazy[k]=x;
        evaluate(k,l,r);
        return;
    }
    add(a,b,x,k*2+1,l,(l+r)/2);
    add(a,b,x,k*2+2,(l+r)/2,r);
    update(k);
}

int get(int a,int b,int x,int k=0,int l=0,int r=SIZE){
    evaluate(k,l,r);
    if(r<=a||b<=l)return 0;
    if(a<=l&&r<=b){
        if(x==1)return datA[k];
        return datB[k];
    }
    return get(a,b,x,k*2+1,l,(l+r)/2)+get(a,b,x,k*2+2,(l+r)/2,r);
}

int N,Q;


int main(){
    scanf("%d%d",&N,&Q);
    init();
    long long PointA=0,PointB=0;
    while(Q--){
        int type,l,r;
        scanf("%d%d%d",&type,&l,&r);
        r++;
        if(type==0){
            int a=get(l,r,1);
            int b=get(l,r,2);
            if(a>b)PointA+=a;
            else if(a<b)PointB+=b;
        }
        else if(type==1){
            add(l,r,1);
        }
        else{
            add(l,r,2);
        }
    }

    PointA+=datA[0];
    PointB+=datB[0];

    printf("%lld %lld\n",PointA,PointB);

    return 0;
}
0