結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー pekempeypekempey
提出日時 2015-08-27 12:38:16
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 276 ms / 5,000 ms
コード長 3,839 bytes
コンパイル時間 1,623 ms
コンパイル使用メモリ 166,456 KB
実行使用メモリ 22,844 KB
最終ジャッジ日時 2023-09-25 18:53:26
合計ジャッジ時間 4,121 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
9,492 KB
testcase_01 AC 3 ms
9,516 KB
testcase_02 AC 3 ms
9,516 KB
testcase_03 AC 3 ms
9,512 KB
testcase_04 AC 3 ms
9,580 KB
testcase_05 AC 4 ms
9,924 KB
testcase_06 AC 15 ms
9,960 KB
testcase_07 AC 4 ms
9,556 KB
testcase_08 AC 7 ms
9,800 KB
testcase_09 AC 128 ms
16,248 KB
testcase_10 AC 123 ms
13,736 KB
testcase_11 AC 71 ms
13,016 KB
testcase_12 AC 126 ms
16,196 KB
testcase_13 AC 21 ms
10,224 KB
testcase_14 AC 84 ms
14,048 KB
testcase_15 AC 107 ms
13,992 KB
testcase_16 AC 211 ms
18,488 KB
testcase_17 AC 276 ms
22,692 KB
testcase_18 AC 155 ms
22,844 KB
testcase_19 AC 158 ms
21,156 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘std::ostream& operator<<(std::ostream&, const std::pair<_T1, _T2>&)’:
main.cpp:81:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, a) rep2 (i, 0, a)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a) repr2 (i, 0, a)
#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
using namespace std;
typedef long long ll;

const ll mod = (ll)1e18 + 9;

ll weight[1010101];
ll wsum[1010101];
ll N, Q;
ll x[202020], l[202020], r[202020];

const int M = 2;

struct SegmentTree {
    int size;
    vector<ll> seg;
    vector<int> lazy; // -1: none, 1: set 0: reset
    SegmentTree(int n) {
        size = 1;	
        while (size < n) size *= 2;
        seg.resize(size * 2 - 1);
        lazy.resize(size * 2 - 1);
    }
    void evallazy(int k, int l, int r) {
    	if (lazy[k] == -1) return;
    	if (lazy[k]) {
    		seg[k] = wsum[r] - wsum[l];	
    	} else {
    		seg[k] = 0;
    	}
    	if (r - l > 1) {
    		lazy[k * 2 + 1] = lazy[k];
    		lazy[k * 2 + 2] = lazy[k];
    	}
    	lazy[k] = -1;
    }
    // q=0:set, q=1:reset
    void update(int a, int b, int q, int k, int l, int r) {
        evallazy(k, l, r);
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) {
            if (q == 0) {
                lazy[k] = 1;
            } else {
            	lazy[k] = 0;
            }
            evallazy(k, l, r);
        } else {
            update(a, b, q, k * 2 + 1, l, (l + r) / 2);
            update(a, b, q, k * 2 + 2, (l + r) / 2, r);
            seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2];
        }
    }
    void update(int a, int b, int q) {
        update(a, b, q, 0, 0, size);
    }
    ll query(int a, int b, int k, int l, int r) {
        evallazy(k, l, r);
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return seg[k];
        ll res = 0;
        res += query(a, b, k * 2 + 1, l, (l + r) / 2);
        res += query(a, b, k * 2 + 2, (l + r) / 2, r);
        return res;
    }
    ll query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
    ll query() {
        return query(0, size);
    }
};

template<class T1, class T2>
ostream &operator <<(ostream &os, const pair<T1, T2> &p) {
    cout << "(" << p.first << " " << p.second << ")";
}

template<class T>
ostream &operator <<(ostream &os, const vector<T> &v) {
    rep (i, v.size()) {
        if (i) cout << " ";
        cout << v[i];
    }
    return os;
}

int main() {
    cin >> N >> Q;
    rep (i, Q) {
        cin >> x[i] >> l[i] >> r[i];
    }
    if (Q == 0) {
        vector<ll> score(M);
        cout << score << endl;
        return 0;
    }
    vector<ll> xs;
    rep (i, Q) {
        xs.push_back(l[i]);
        xs.push_back(l[i] + 1);
        xs.push_back(r[i]);
        xs.push_back(r[i] + 1);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    ll w = xs.size();
    rep (i, xs.size() - 1) {
        weight[i] = xs[i + 1] - xs[i];
    }
    rep (i, Q) {
        l[i] = lower_bound(xs.begin(), xs.end(), l[i]) - xs.begin();
        r[i] = lower_bound(xs.begin(), xs.end(), r[i]) - xs.begin();
    }
    partial_sum(weight, weight + w, wsum + 1);

    // main logic

    vector<SegmentTree> segt(M, SegmentTree(w + 10));
    vector<ll> score(M);
    rep (i, Q) {
        if (x[i] == 0) {
            vector<pair<ll, ll>> t(M);
            rep (j, M) {
                t[j].second = j;
                t[j].first = segt[j].query(l[i], r[i] + 1);
            }
            sort(t.rbegin(), t.rend());
            if (t[0].first > t[1].first) {
                score[t[0].second] += t[0].first;
                score[t[0].second] %= mod;
            }
        } else {
            x[i]--;
            rep (j, M) {
                segt[j].update(l[i], r[i] + 1, x[i] != j);
            }
        }
    }

    rep (i, M) {
        score[i] += segt[i].query();
        score[i] %= mod;
    }

    cout << score << endl;

    return 0;
}
0