結果

問題 No.230 Splarraay スプラレェーイ
ユーザー parukiparuki
提出日時 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 -
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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){
// lazylazy
// 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){
// indexlazypropagate
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();
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0