結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー ctyl_0ctyl_0
提出日時 2015-11-10 15:15:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 132 ms / 5,000 ms
コード長 3,020 bytes
コンパイル時間 1,071 ms
コンパイル使用メモリ 98,540 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2024-09-13 14:20:32
合計ジャッジ時間 2,752 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 9 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 4 ms
5,376 KB
testcase_09 AC 64 ms
5,376 KB
testcase_10 AC 80 ms
5,376 KB
testcase_11 AC 41 ms
5,376 KB
testcase_12 AC 63 ms
5,376 KB
testcase_13 AC 13 ms
5,376 KB
testcase_14 AC 73 ms
7,168 KB
testcase_15 AC 115 ms
7,168 KB
testcase_16 AC 124 ms
7,296 KB
testcase_17 AC 132 ms
7,168 KB
testcase_18 AC 104 ms
7,168 KB
testcase_19 AC 92 ms
7,168 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define var auto
#define mod 1000000007
#define inf 2147483647
#define nil -1
typedef long long ll;

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
}

template <typename T>
void output(T a, int precision) {
    if(precision > 0){
        cout << fixed << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

int sz;

class segtree_lazy{
private:
    int n;
    // static int sz;
    
public:
    vector<int> isfull, to; // isfull : 1 / 0 / -1 : full / empty / mixed, to: total
    
    segtree_lazy(int a){
        n = 1;
        while(n < a){
            n *= 2;
        }
        sz = n;
        isfull.resize(2 * n - 1, 0); // 0-indexed
        to.resize(2 * n - 1, 0); // 0-indexed
    }
    
    // sum up range if the range is full or empty
    int sum(int x, int y, int l = 0, int r = sz, int k = 0){ // [x, y)
        if(r <= x || y <= l) return 0;
        if(x <= l && r <= y) return to[k];
        x = max(x, l);
        y = min(y, r);
        if(isfull[k] >= 0) return isfull[k] ? (y - x) : 0;
        return sum(x, y, l, (l + r) / 2, k * 2 + 1) + sum(x, y, (l + r) / 2, r, k * 2 + 2);
    }
    
    // update cells
    void update(int x, int y, int v, int l = 0, int r = sz, int k = 0) { // [x, y)
        if(x <= l && r <= y) {
            isfull[k] = v;
            to[k] = isfull[k] ? (r - l) : 0;
        }
        else if(l < y && x < r) {
            if(isfull[k] >= 0) {
                isfull[k * 2 + 1] = isfull[k * 2 + 2] = isfull[k];
                to[k * 2 + 1] = to[k * 2 + 2] = isfull[k] ? (r - l) / 2 : 0;
                isfull[k] = -1;
            }
            update(x, y, v, l, (l + r) / 2, k * 2 + 1);
            update(x, y, v, (l + r) / 2, r, k * 2 + 2);
            to[k] = to[k * 2 + 1] + to[k * 2 + 2];
        }
    }
    
    
};

// end of template

int main() {
    cin.tie(0);
    // source code
    int N = inputValue();
    int Q = inputValue();
    
    segtree_lazy A(N), B(N);
    
    ll ptA = 0;
    ll ptB = 0;
    
    rep(i, Q){
        int x = inputValue();
        int l = inputValue();
        int r = inputValue() + 1;
        if (x == 1) {
            A.update(l, r, 1);
            B.update(l, r, 0);
        }
        else if (x == 2){
            A.update(l, r, 0);
            B.update(l, r, 1);
        }
        else{
            int tptA = A.sum(l, r);
            int tptB = B.sum(l, r);
            if (tptA > tptB) {
                ptA += tptA;
            }
            else if (tptA < tptB){
                ptB += tptB;
            }
        }
    }
    ptA += A.sum(0, N);
    ptB += B.sum(0, N);
    
    cout << ptA << " " << ptB << endl;
    
    return 0;
}
0