結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー latte0119
提出日時 2015-10-31 17:33:09
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 122 ms / 5,000 ms
コード長 2,041 bytes
コンパイル時間 484 ms
コンパイル使用メモリ 60,540 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-13 06:24:55
合計ジャッジ時間 2,622 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:73:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   73 |     scanf("%d%d",&N,&Q);
      |     ~~~~~^~~~~~~~~~~~~~
main.cpp:78:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   78 |         scanf("%d%d%d",&type,&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

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