結果
問題 | No.230 Splarraay スプラレェーイ |
ユーザー | paruki |
提出日時 | 2016-08-12 01:20:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,003 bytes |
コンパイル時間 | 1,853 ms |
コンパイル使用メモリ | 179,484 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-11-07 11:55:13 |
合計ジャッジ時間 | 4,893 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 3 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | AC | 64 ms
10,880 KB |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | AC | 133 ms
10,752 KB |
testcase_19 | WA | - |
ソースコード
#include "bits/stdc++.h"using namespace std;#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))#define rep(i,j) FOR(i,0,j)#define each(x,y) for(auto &(x):(y))#define mp make_pair#define all(x) (x).begin(),(x).end()#define debug(x) cout<<#x<<": "<<(x)<<endl#define smax(x,y) (x)=max((x),(y))#define smin(x,y) (x)=min((x),(y))#define MEM(x,y) memset((x),(y),sizeof (x))#define sz(x) (int)(x).size()typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;typedef vector<ll> vll;struct LazySegTree{int dataSize;vi val, lazy;vector<bool> lazyZero;LazySegTree(int n){dataSize = 1;while(dataSize < n)dataSize *= 2;int treeSize = 2 * dataSize - 1;val = lazy = vi(treeSize);lazyZero = vector<bool>(treeSize);}void propagate(int index, int curL, int curR){// 自分の値をlazyにもとづいて書き換えて自分のlazyをクリア。// 子のlazyを書き換える。if(lazyZero[index]){val[index] = 0;}val[index] += lazy[index] * (curR-curL);if(curR - curL > 1){int l = index * 2 + 1, r = index * 2 + 2;if(lazyZero[index]){lazy[l] = lazy[r] = 0;lazyZero[l] = lazyZero[r] = true;}lazy[l] |= lazy[index];lazy[r] |= lazy[index];}lazy[index] = 0;lazyZero[index] = false;}// [curL, curR) を評価するvoid update(int index, int curL, int curR, int givenL, int givenR, bool isAdd){// 範囲外であろうとpropagateは必ず呼ぶ。そうでないと、親がうまく評価されないpropagate(index, curL, curR);// 範囲外if(curR <= givenL || givenR <= curL)return;// 範囲内if(givenL <= curL && curR <= givenR){// 直接書き換えないでindexのlazyを書き換えてpropagateを呼ぶif(!isAdd){lazyZero[index] = true;lazy[index] = 0;}else{lazy[index] |= 1;}propagate(index, curL, curR);} else{ // 範囲外と範囲内が含まれる(長さ2以上)int mid = (curL + curR) / 2;update(index * 2 + 1, curL, mid, givenL, givenR, isAdd);update(index * 2 + 2, mid, curR, givenL, givenR, isAdd);val[index] = val[index * 2 + 1] + val[index * 2 + 2];}}void update(int l, int r, bool isAdd){update(0, 0, dataSize, l, r, isAdd);}int query(int l, int r){return query(0, 0, dataSize, l, r);}int query(int index, int curL, int curR, int givenL, int givenR){// 範囲外if(curR <= givenL || givenR <= curL)return 0;propagate(index, curL, curR);if(givenL <= curL && curR <= givenR){return val[index];} else{int mid = (curL + curR) / 2;int res1 = query(index * 2 + 1, curL, mid, givenL, givenR);int res2 = query(index * 2 + 2, mid, curR, givenL, givenR);return res1 + res2;}}};const int MAX = (int)1e5 + 1;int N, Q, X[MAX], L[MAX], R[MAX];void solve(){vll ans(2);vector<LazySegTree> segTree(2, LazySegTree(N));rep(i, Q){R[i]++;X[i]--;if(X[i] == -1){vll val(2);rep(j, 2)val[j] = segTree[j].query(L[i], R[i]);if(val[0] > val[1])ans[0] += val[0];else if(val[1] > val[0])ans[1] += val[1];} else{segTree[X[i]].update(L[i], R[i], true);segTree[1-X[i]].update(L[i], R[i], false);}}rep(i, 2)ans[i] += segTree[i].query(0, N);cout << ans[0] << ' ' << ans[1] << endl;}int main(){while(cin >> N >> Q){rep(i, Q)scanf("%d%d%d", &X[i], &L[i], &R[i]);solve();}}