結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー chocoruskchocorusk
提出日時 2019-05-28 13:36:48
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 222 ms / 5,000 ms
コード長 2,266 bytes
コンパイル時間 1,014 ms
コンパイル使用メモリ 105,900 KB
実行使用メモリ 11,384 KB
最終ジャッジ日時 2023-10-17 18:22:56
合計ジャッジ時間 4,024 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 1 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 12 ms
4,348 KB
testcase_07 AC 3 ms
4,348 KB
testcase_08 AC 4 ms
4,348 KB
testcase_09 AC 101 ms
7,424 KB
testcase_10 AC 91 ms
4,348 KB
testcase_11 AC 56 ms
5,312 KB
testcase_12 AC 99 ms
7,424 KB
testcase_13 AC 16 ms
4,348 KB
testcase_14 AC 85 ms
11,384 KB
testcase_15 AC 141 ms
11,384 KB
testcase_16 AC 178 ms
11,384 KB
testcase_17 AC 222 ms
11,384 KB
testcase_18 AC 129 ms
11,384 KB
testcase_19 AC 131 ms
11,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll INF=1e9;
struct RSQandRUQ{
    vector<ll> sum, part;
    int n, m;
    RSQandRUQ(int size):n(size){
        m=1;
        while(m<n) m<<=1;
        sum.resize(2*m);
        part.resize(2*m);
    }
    void eval(int k, int l, int r){
        if(part[k]<INF){
            sum[k]=part[k]*(ll)(r-l);
            if(k<m-1){
                part[2*k+1]=part[k];
                part[2*k+2]=part[k];
            }
            part[k]=INF;
        }
    }
    void update(int a, int b, ll x, int k, int l, int r){
        eval(k, l, r);
        if(r<=a || b<=l) return;
        if(a<=l && r<=b){
            part[k]=x;
            eval(k, l, r);
        }else{
            update(a, b, x, 2*k+1, l, (l+r)/2);
            update(a, b, x, 2*k+2, (l+r)/2, r);
            sum[k]=sum[2*k+1]+sum[2*k+2];
        }
    }
    ll getsum(int a, int b, int k, int l, int r){
        eval(k, l, r);
        if(b<=l || r<=a) return 0;
        if(a<=l && r<=b) return sum[k];
        else return getsum(a, b, 2*k+1, l, (l+r)/2)+getsum(a, b, 2*k+2, (l+r)/2, r);
    }
    void update(int a, int b, ll x){
        update(a, b, x, 0, 0, m);
    }
    ll getsum(int a, int b){
        return getsum(a, b, 0, 0, m);
    }
};

int main()
{
    int n, q; cin>>n>>q;
    RSQandRUQ a(n), b(n);
    ll ansa=0, ansb=0;
    for(int i=0; i<q; i++){
        int x, l, r; cin>>x>>l>>r;
        if(x==0){
            ll s=b.getsum(l, r+1), t=a.getsum(l, r+1);
            if(s>0) ansa+=(s+t)/2;
            else if(s<0) ansb+=(t-s)/2;
        }else if(x==1){
            a.update(l, r+1, 1);
            b.update(l, r+1, 1);
        }else{
            a.update(l, r+1, 1);
            b.update(l, r+1, -1);
        }
    }
    ll s=b.getsum(0, n), t=a.getsum(0, n);
    ansa+=(s+t)/2;
    ansb+=(t-s)/2;
    cout<<ansa<<" "<<ansb<<endl;
    return 0;
}
0