結果
問題 | No.230 Splarraay スプラレェーイ |
ユーザー | srup٩(๑`н´๑)۶ |
提出日時 | 2016-09-02 02:16:04 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,127 bytes |
コンパイル時間 | 679 ms |
コンパイル使用メモリ | 68,592 KB |
実行使用メモリ | 75,536 KB |
最終ジャッジ日時 | 2024-04-27 14:41:34 |
合計ジャッジ時間 | 7,707 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 8 ms
6,940 KB |
testcase_06 | AC | 407 ms
6,944 KB |
testcase_07 | AC | 4 ms
6,940 KB |
testcase_08 | AC | 9 ms
6,944 KB |
testcase_09 | TLE | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
ソースコード
#include <iostream> #include <algorithm> #include <vector> #include <cstdio> #include <map> typedef long long ll; using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) const int MAX_N = 200010;//頂点数の倍ぐらい持っておかないとダメ? ll seg[MAX_N * 2], lazy[MAX_N * 2] = {-1}; struct segtree{ void lazy_evaluate_node(int k, int l, int r){ if(lazy[k] != -1){ seg[k] = lazy[k] * (r - l); if(r - l > 1){ lazy[k * 2 + 1] = lazy[k]; lazy[k * 2 + 2] = lazy[k]; } lazy[k] = -1; } } //update(a,b,v) := [a,b)を全てvに書き換える void update(int a, int b, ll v, int k = 0, int l = 0, int r = MAX_N){ lazy_evaluate_node(k, l, r);//辿ったノードはついでについでに伝搬しておく if(r <= a || b <= l) return; if(a <= l && r <= b){ lazy[k] = v; lazy_evaluate_node(k, l, r);//一回遅延評価しとかないと都合悪い?? }else{ update(a, b, v, k * 2 + 1, l, (l + r) / 2); update(a, b, v, k * 2 + 2, (l + r) / 2, r); seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2]; } } //get(l,r) := [a,b)に対する総和を求める ll get(int a, int b, int k = 0, int l = 0, int r = MAX_N){ // printf("%d %d\n", a, b); lazy_evaluate_node(k, l, r);//辿ったノードはついでについでに伝搬しておく if(r <= a || b <= l) return 0; if(a <= l && r <= b) return seg[k]; ll x = get(a, b, k * 2 + 1, l, (l + r) / 2); ll y = get(a, b, k * 2 + 2, (l + r) / 2, r); return x + y; } }; int main(void){ int n; cin >> n; int q; cin >> q; segtree st; ll ansa = 0, ansb = 0; rep(i, q){ int x; cin >> x; int left, right; cin >> left >> right; if(x == 0){//ボーナス int sa = 0, sb = 0; for (int j = left; j <= right; ++j){ if(st.get(j, j + 1) == 1) sa++; else if(st.get(j, j + 1) == 2) sb++; } if(sa > sb) ansa += sa; else if(sa < sb) ansb += sb; }else if(x == 1){ st.update(left, right + 1, 1); }else{ st.update(left, right + 1, 2); } } rep(i, n){ if(st.get(i, i + 1) == 1) ansa++; else if(st.get(i, i + 1) == 2) ansb++; } printf("%lld %lld\n", ansa, ansb); return 0; }