結果

問題 No.230 Splarraay スプラレェーイ
ユーザー Kmcode1Kmcode1
提出日時 2015-06-19 23:01:19
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 103 ms / 5,000 ms
コード長 2,533 bytes
コンパイル時間 2,927 ms
コンパイル使用メモリ 106,220 KB
実行使用メモリ 11,944 KB
最終ジャッジ日時 2023-09-21 10:05:39
合計ジャッジ時間 4,727 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 6 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 48 ms
7,564 KB
testcase_10 AC 44 ms
4,376 KB
testcase_11 AC 28 ms
5,660 KB
testcase_12 AC 48 ms
7,648 KB
testcase_13 AC 9 ms
4,380 KB
testcase_14 AC 26 ms
7,680 KB
testcase_15 AC 69 ms
7,712 KB
testcase_16 AC 66 ms
9,644 KB
testcase_17 AC 103 ms
11,864 KB
testcase_18 AC 57 ms
11,944 KB
testcase_19 AC 66 ms
11,672 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<unordered_map>
using namespace std;
#define MAX 200002
int n;
int w;
struct st{
	int sum = 0;
	int lazy = -1;
	int a = 0;
	int b = 0;
};
st seg[MAX * 4];
void update(int a){
	if (seg[a].lazy != -1){
		if (seg[a].lazy == 0){
			seg[a].a = seg[a].sum;
			seg[a].b = 0;
		}
		else{
			seg[a].a = 0;
			seg[a].b = seg[a].sum;
		}
		seg[a * 2 + 1].lazy = seg[a].lazy;
		seg[a * 2 + 2].lazy = seg[a].lazy;
		seg[a].lazy = -1;
	}
}
inline void init(int b, int l, int r){
	seg[b].sum = r - l;
	if (l + 1 == r){
		return;
	}
	init(b * 2 + 1, l, (l + r) >> 1);
	init(b * 2 + 2, (l + r) >> 1, r);
}
inline void add(int b, int l, int r, int ll, int rr,int x){
	update(b);
	if (ll <= l&&r <= rr){
		seg[b].lazy = x;
		update(b);
		return;
	}
	if (r<=ll || rr <= l){
		return;
	}
	add(b * 2 + 1, l, (l + r) >> 1, ll, rr, x);
	add(b * 2 + 2, (l + r) >> 1, r, ll, rr, x);
	seg[b].a = seg[b * 2 + 1].a + seg[b * 2 + 2].a;
	seg[b].b = seg[b * 2 + 1].b + seg[b * 2 + 2].b;
	seg[b].lazy = -1;
}
inline pair<int, int> q(int b, int l, int r, int ll, int rr){
	update(b);
	if (r <= ll || rr <= l){
		return make_pair(0, 0);
	}
	if (ll <= l&&r <= rr){
		return make_pair(seg[b].a, seg[b].b);
	}
	pair<int, int> R;
	R = q(b * 2 + 1, l, (l + r) >> 1, ll, rr);
	pair<int, int> f = q(b * 2 + 2, (l + r) >> 1, r, ll, rr);
	R.first += f.first;
	R.second += f.second;
	return R;
}

int main(){
	scanf("%d", &n);
	int qq;
	scanf("%d", &qq);
	long long int ans = 0;
	long long int ans1 = 0;
	init(0, 0, n);
	while (qq--){
		int ty;
		scanf("%d", &ty);
		if (ty == 0){
			int l, r;
			scanf("%d%d", &l, &r);
			pair<int, int> k = q(0, 0, n, l, r + 1);
			if (k.first == k.second){
				continue;
			}
			if (k.first > k.second){
				ans += (long long int)(k.first);
			}
			else{
				ans1 += (long long int)(k.second);
			}
			continue;
		}
		int l, r;
		scanf("%d%d", &l, &r);
		if (ty == 1){
			add(0, 0, n, l, r + 1, 0);
		}
		else{
			add(0, 0, n, l, r + 1, 1);
		}
	}
	pair<int, int> k = q(0, 0, n, 0, n);
	ans += (long long int)(k.first);
	ans1 += (long long int)(k.second);
	printf("%lld %lld\n", ans, ans1);
	return 0;
}
0