結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー nebukuro09nebukuro09
提出日時 2017-04-07 16:31:27
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 233 ms / 5,000 ms
コード長 2,688 bytes
コンパイル時間 624 ms
コンパイル使用メモリ 103,276 KB
実行使用メモリ 9,832 KB
最終ジャッジ日時 2023-09-03 12:43:30
合計ジャッジ時間 3,293 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 3 ms
4,376 KB
testcase_06 AC 12 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 4 ms
4,376 KB
testcase_09 AC 106 ms
5,928 KB
testcase_10 AC 103 ms
4,376 KB
testcase_11 AC 61 ms
4,588 KB
testcase_12 AC 110 ms
5,928 KB
testcase_13 AC 19 ms
4,380 KB
testcase_14 AC 89 ms
7,788 KB
testcase_15 AC 176 ms
9,048 KB
testcase_16 AC 197 ms
9,260 KB
testcase_17 AC 233 ms
9,832 KB
testcase_18 AC 146 ms
7,792 KB
testcase_19 AC 134 ms
7,748 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto N = readln.chomp.to!int;
    auto Q = readln.chomp.to!int;

    auto st = new LazySegmentTree!(int)(N);
    auto st2 = new LazySegmentTree!(int)(N);
    long score1 = 0;
    long score2 = 0;
    
    foreach (q; 0..Q) {
        auto s = readln.split.map!(to!int);
        auto x = s[0];
        auto l = s[1];
        auto r = s[2];
        
        if (x == 0) {
            auto used = st2.getVal(l, r);
            auto m = st.getVal(l, r);
            auto a = (used + m) / 2;
            auto b =  used - a;
            if (m > 0) score1 += a;
            if (m < 0) score2 += b;
        }
        else if (x == 1) {
            st.assign(l, r, 1);
            st2.assign(l, r, 1);
        }
        else if (x == 2) {
            st.assign(l, r, -1);
            st2.assign(l, r, 1);
        }

    }

    auto used = st2.getVal(0, N-1);
    auto m = st.getVal(0, N-1);
    auto a = (used + m) / 2;
    auto b =  used - a;
    score1 += a;
    score2 += b;
    
    writeln(score1, " ", score2);
}


class LazySegmentTree(T) {
    T[] table;
    T[] lazy_;
    int size;
 
    this(int n) {
        assert(bsr(n) < 29);
        size = 1 << (bsr(n) + 2);
        table = new T[](size);
        lazy_ = new T[](size);
        fill(table, 0);
        fill(lazy_, 0);
    }

    void eval(int i, int l, int r) {
        if (lazy_[i] == 0) return;

        table[i] = lazy_[i] * (r - l + 1);
        if (l != r) {
            lazy_[i*2+1] = lazy_[i];
            lazy_[i*2+2] = lazy_[i];
        }

        lazy_[i] = 0;
        
        return;
    }

    void assign(int a, int b, T num) {
        return assign(a, b, num, 0, 0, size/2-1);
    }
 
    void assign(int a, int b, T num, int i, int l, int r) {
        eval(i, l, r);
        
        if (a > r || b < l) return;
        if (lazy_[i] == num) return;
        if (a <= l && r <= b) {
            lazy_[i] = num;
            eval(i, l, r);
            return;
        }
        else {
            assign(a, b, num, i*2+1, l, (l+r)/2);
            assign(a, b, num, i*2+2, (l+r)/2+1, r);
            table[i] = table[i*2+1] + table[i*2+2];
        }
    }
 
    T getVal(int a, int b) {
        return getVal(a, b, 0, 0, size/2-1);
    }
 
    T getVal(int a, int b, int i, int l, int r) {
        eval(i, l, r);
        
        if (a > r || b < l) return 0;
        if (a <= l && r <= b) return table[i];
        return
            getVal(a, b, i*2+1, l, (l+r)/2) +
            getVal(a, b, i*2+2, (l+r)/2+1, r);
    }
}
0