結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー airisairis
提出日時 2015-06-29 23:51:10
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 192 ms / 5,000 ms
コード長 3,632 bytes
コンパイル時間 1,147 ms
コンパイル使用メモリ 88,788 KB
実行使用メモリ 12,812 KB
最終ジャッジ日時 2023-09-22 04:34:09
合計ジャッジ時間 3,293 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
11,608 KB
testcase_01 AC 4 ms
11,636 KB
testcase_02 AC 5 ms
11,516 KB
testcase_03 AC 4 ms
11,496 KB
testcase_04 AC 5 ms
11,620 KB
testcase_05 AC 5 ms
11,660 KB
testcase_06 AC 13 ms
11,648 KB
testcase_07 AC 6 ms
11,584 KB
testcase_08 AC 7 ms
11,696 KB
testcase_09 AC 91 ms
12,228 KB
testcase_10 AC 86 ms
12,704 KB
testcase_11 AC 54 ms
11,908 KB
testcase_12 AC 89 ms
12,172 KB
testcase_13 AC 18 ms
11,680 KB
testcase_14 AC 74 ms
12,732 KB
testcase_15 AC 128 ms
12,740 KB
testcase_16 AC 157 ms
12,696 KB
testcase_17 AC 192 ms
12,812 KB
testcase_18 AC 113 ms
12,732 KB
testcase_19 AC 118 ms
12,188 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <numeric>
#include <bitset>
#include <complex>
#define rep(x, to) for (int x = 0; x < (to); x++)
#define REP(x, a, to) for (int x = (a); x < (to); x++)
#define foreach(itr, x) for (typeof((x).begin()) itr = (x).begin(); itr != (x).end(); itr++)
#define EPS (1e-14)

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef complex<double> Complex;
typedef vector< vector<int> > Mat;

// 遅延評価SegmentTree
struct LazyPropagationSegmentTree {
	int n;						// 2のべき乗値
	ll lazy[1 << 18];	// 2*nのサイズ以上を設定すること
	ll  dat[1 << 18];	// 2*nのサイズ以上を設定すること
	void init(int m) {
		n = 1;
		while (n < m) n *= 2;
		memset(lazy, -1, sizeof(lazy));
		memset(dat, 0, sizeof(dat));
	}
	// 区間[a,b)をxにする
	// k,l,rは現在ノードkに着目し、ノードkは区間[l,r)を指すことを示す
	void update(int a, int b, int x, int k, int l, int r) {
		if (lazy[k] != -1) {
			dat[k] = (r - l) * lazy[k];
			if (k < n - 1) {
				lazy[2 * k + 1] = lazy[k];
				lazy[2 * k + 2] = lazy[k];
			}
			lazy[k] = -1;
		}
		if (b <= l || r <= a) return;
		if (a <= l && r <= b) {
			dat[k] = (r - l) * x;
			//葉じゃない
			if (k < n - 1) {
				lazy[2 * k + 1] = x;
				lazy[2 * k + 2] = x;
			}
			return;
		}
		int m = (l + r) / 2;
		int chl = 2 * k + 1;
		int chr = 2 * k + 2;
		update(a, b, x, chl, l, m);
		update(a, b, x, chr, m, r);
		dat[k] = dat[chl] + dat[chr];
		lazy[k] = -1;
	}
	// 区間[a,b)の値を参照する
	// k,l,rは現在ノードkに着目し、ノードkは区間[l,r)を指すことを示す
	ll query(int a, int b, int k, int l, int r) {
		if (lazy[k] != -1) {
			dat[k] = (r - l) * lazy[k];
			// 伝播が必要なのはkの子のノードなので伝播させる(kが葉であれば伝播不要)
			if (k < n - 1) {
				lazy[2 * k + 1] = lazy[k];
				lazy[2 * k + 2] = lazy[k];
			}
			lazy[k] = -1;
		}
		if (b <= l || r <= a) return 0;
		if (a <= l && r <= b) return dat[k];
		int m = (l + r) / 2;
		int chl = 2 * k + 1;
		int chr = 2 * k + 2;
		return query(a, b, chl, l, m) + query(a, b, chr, m, r);
	}
};

int N;
int Q;
int X[100005];
int L[100005];
int R[100005];
ll ans_a, ans_b;

LazyPropagationSegmentTree seg_a, seg_b;

void debug(LazyPropagationSegmentTree &seg) {
	rep(i, 2 * seg.n - 1) {
		printf("lazy[%d]=%d dat[%d]=%d\n", i, seg.lazy[i], i, seg.dat[i]);
	}
	printf("-----\n");
}

void solve() {
	seg_a.init(N);
	seg_b.init(N);
	rep(i, Q) {
		int x = X[i], l = L[i], r = R[i];
		if (x == 0) {
			int a = seg_a.query(l, r + 1, 0, 0, seg_a.n);
			int b = seg_b.query(l, r + 1, 0, 0, seg_b.n);
			if (a > b) {
				ans_a += a;
			} else if (a < b) {
				ans_b += b;
			}
		} else if (x == 1) {
			seg_a.update(l, r + 1, 1, 0, 0, seg_a.n);
			seg_b.update(l, r + 1, 0, 0, 0, seg_b.n);
			//debug(seg_a);
		} else {
			seg_a.update(l, r + 1, 0, 0, 0, seg_a.n);
			seg_b.update(l, r + 1, 1, 0, 0, seg_b.n);
			//debug(seg_a);
		}
	}
	ans_a += seg_a.query(0, seg_a.n, 0, 0, seg_a.n);
	ans_b += seg_b.query(0, seg_b.n, 0, 0, seg_b.n);
#if 0
	rep(i, N) {
		cout << seg_a.query(i, i + 1, 0, 0, seg_a.n) << " ";
	} cout << endl;
	rep(i, N) {
		cout << seg_b.query(i, i + 1, 0, 0, seg_b.n) << " ";
	} cout << endl;
#endif
	cout << ans_a << " " << ans_b << endl;
}

int main() {
	cin >> N;
	cin >> Q;
	rep(i, Q) {
		cin >> X[i] >> L[i] >> R[i];
	}
	solve();
	return 0;
}
0