結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー chocorusk
提出日時 2019-05-28 13:36:48
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 174 ms / 5,000 ms
コード長 2,266 bytes
コンパイル時間 949 ms
コンパイル使用メモリ 105,556 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-09-17 15:39:07
合計ジャッジ時間 3,669 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

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