結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー ctyl_0ctyl_0
提出日時 2015-11-10 05:07:47
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,777 bytes
コンパイル時間 1,045 ms
コンパイル使用メモリ 100,980 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2024-09-13 14:18:30
合計ジャッジ時間 3,574 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 3 ms
6,944 KB
testcase_06 AC 9 ms
6,944 KB
testcase_07 AC 3 ms
6,940 KB
testcase_08 AC 4 ms
6,940 KB
testcase_09 AC 64 ms
6,944 KB
testcase_10 AC 79 ms
6,940 KB
testcase_11 AC 41 ms
6,944 KB
testcase_12 AC 64 ms
6,944 KB
testcase_13 AC 12 ms
6,940 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 126 ms
7,296 KB
testcase_17 AC 132 ms
7,296 KB
testcase_18 AC 105 ms
7,296 KB
testcase_19 AC 89 ms
7,296 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;

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

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


class rmq {
private:
    int n;
    int sz;
public:
    vector<ll> v;
    rmq(int a){
        n = 1;
        for(; n * 2 < a;){
            n *= 2;
        }
        sz = n * 2;
        v.resize(4 * n - 1, inf);
    }
    
    void update(int i, ll x){
        i += sz - 1;
        v[i] = x;
        while(i > 0){
            i = (i - 1) / 2;
            v[i] = min(v[2 * i + 1], v[2 * i + 2]);
        }
    }
    
    ll query_(int a, int b, int k, int l, int r){
        if(r <= a || b <= l) return inf;
        if(a <= l && r <= b) return v[k];
        else{
            ll vl = query_(a, b, k * 2 + 1, l, (l + r) / 2);
            ll vr = query_(a, b, k * 2 + 2, (l + r) / 2, r);
            return min(vl, vr);
        }
    }
    
    ll query(int a, int b){
        return query_(a, b, 0, 0, sz);
    }
};

int sz;

class segtree_lazy{
private:
    int n;
    // static int sz;
public:
    vector<int> isfull, to; // isfull : 1 / 0 / -1 : full / empty / mixed, to: count
    
    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
    }
    
    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);
    }
    
    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);
    
    int ptA = 0;
    int 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