結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー toma
提出日時 2019-09-26 04:23:36
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 195 ms / 5,000 ms
コード長 3,737 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,796 ms
コンパイル使用メモリ 178,072 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-23 07:02:27
合計ジャッジ時間 4,371 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
using pii = pair<int, int>;

template<typename Monoid, typename OperatorMonoid = Monoid>
class LazySegmentTree {
private:
	using F = function<Monoid(Monoid, Monoid)>;
	using G = function<Monoid(Monoid, OperatorMonoid, int)>;
	using H = function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;

	int sz; // 対応する配列の幅
	vector<Monoid> data;
	vector<OperatorMonoid> lazy;
	const F f; // 2区間マージ演算(data-data-ボトムアップマージ)
	const G g; // 要素,作用素マージ演算(lazy->data同位置変換時の、(data,lazy,len)の計算)
	const H h; // 作用素マージ演算　(query->lazyトップダウン伝搬時の、(lazy,query_value)の計算)
	const Monoid M1;          // モノイド単位元　(data単位元)
	const OperatorMonoid OM0; // 作用素単位元 (lazy単位元)

	void propagate(int idx, int len) {
		// 幅lenのlazy[idx]が存在するとき、値を下に流す
		if (lazy[idx] != OM0) {
			if (idx < sz) {
				lazy[(idx << 1) | 0] = h(lazy[(idx << 1) | 0], lazy[idx]);
				lazy[(idx << 1) | 1] = h(lazy[(idx << 1) | 1], lazy[idx]);
			}
			data[idx] = g(data[idx], lazy[idx], len);
			lazy[idx] = OM0;
		}
	}
	Monoid update_impl(int a, int b, const OperatorMonoid& val, int idx, int l, int r) {
		propagate(idx, r - l);
		if (r <= a || b <= l)return data[idx];
		else if (a <= l && r <= b) {
			lazy[idx] = h(lazy[idx], val);
			propagate(idx, r - l);
			return data[idx];
		}
		else return data[idx] = f(
			update_impl(a, b, val, (idx << 1) | 0, l, (l + r) >> 1),
			update_impl(a, b, val, (idx << 1) | 1, (l + r) >> 1, r)
		);
	}
	Monoid query_impl(int a, int b, int idx, int l, int r) {
		propagate(idx, r - l);
		if (r <= a || b <= l)return M1;
		else if (a <= l && r <= b)return data[idx];
		else return f(
			query_impl(a, b, (idx << 1) | 0, l, (l + r) >> 1),
			query_impl(a, b, (idx << 1) | 1, (l + r) >> 1, r)
		);
	}

public:
	// init忘れに注意
	LazySegmentTree(int n, const F f, const G g, const H h,
		const Monoid& M1, const OperatorMonoid OM0)
		:f(f), g(g), h(h), M1(M1), OM0(OM0) {
		sz = 1;
		while (sz < n)sz <<= 1;
		data.assign(2 * sz, M1);
		lazy.assign(2 * sz, OM0);
	}
	void build(const vector<Monoid>& vals) {
		rep(idx, vals.size())data[idx + sz] = vals[idx];
		for (int idx = sz - 1; idx > 0; idx--) {
			data[idx] = f(data[(idx << 1) | 0], data[(idx << 1) | 1]);
		}
	}
	Monoid update(int a, int b, const OperatorMonoid& val) {
		return update_impl(a, b, val, 1, 0, sz);
	}
	Monoid query(int a, int b) {
		return query_impl(a, b, 1, 0, sz);
	}
	Monoid operator[](const int& idx) {
		return query(idx, idx + 1);
	}
};

int main()
{
	int N, Q;
	cin >> N >> Q;

	auto f = [](pii l, pii r) {
		return make_pair(l.first + r.first, l.second + r.second);
	};
	auto g = [](pii data, int lazy, int len) {
		switch (lazy) {
		case 1: return make_pair(len, 0);
		case 0:return data;
		case -1:return make_pair(0, len);
		default: return make_pair(-1, -1);
		}
	};
	auto h = [](int lazy, int query) {
		return (query != 0 ? query : lazy);
	};
	LazySegmentTree<pii, int> seg(N, f, g, h, { 0,0 }, 0);

	ll scoreA = 0, scoreB = 0;
	rep(q, Q) {
		int x, l, r;
		cin >> x >> l >> r;
		switch (x) {
		case 1:
			seg.update(l, r + 1, 1);
			break;
		case 2:
			seg.update(l, r + 1, -1);
			break;
		case 0:
			auto res = seg.query(l, r + 1);
			if (res.first == res.second)continue;
			(res.first > res.second ? scoreA : scoreB)
				+= max(res.first, res.second);
			break;
		}
	}
	auto last = seg.query(0, N);
	scoreA += last.first;
	scoreB += last.second;
	cout << scoreA << " " << scoreB << endl;
	return 0;
}
0