#382974 (C++14) No.318 学学学学学

• 問題: No.318 学学学学学
• ユーザー: toma
• 提出日時: 2019-09-24 22:43:16
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 239 ms / 2,000 ms
• コード長: 3,299 bytes
• コンパイル時間: 1,893 ms
• コンパイル使用メモリ: 188,072 KB
• 実行使用メモリ: 22,356 KB
• 最終ジャッジ日時: 2023-10-19 17:09:22
• 合計ジャッジ時間: 7,591 ms
• ジャッジサーバーID （参考情報）: judge14 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	15 ms; 5,196 KB
testcase_01	AC	31 ms; 7,044 KB
testcase_02	AC	38 ms; 7,572 KB
testcase_03	AC	25 ms; 5,988 KB
testcase_04	AC	33 ms; 7,044 KB
testcase_05	AC	239 ms; 22,356 KB
testcase_06	AC	228 ms; 17,604 KB
testcase_07	AC	197 ms; 16,020 KB
testcase_08	AC	172 ms; 14,700 KB
testcase_09	AC	145 ms; 13,908 KB
testcase_10	AC	122 ms; 13,116 KB
testcase_11	AC	234 ms; 22,356 KB
testcase_12	AC	189 ms; 17,604 KB
testcase_13	AC	149 ms; 16,020 KB
testcase_14	AC	132 ms; 14,700 KB
testcase_15	AC	116 ms; 13,908 KB
testcase_16	AC	101 ms; 13,116 KB
testcase_17	AC	128 ms; 17,604 KB
testcase_18	AC	116 ms; 17,604 KB
testcase_19	AC	128 ms; 17,604 KB
testcase_20	AC	84 ms; 13,116 KB
testcase_21	AC	1 ms; 4,348 KB
testcase_22	AC	2 ms; 4,348 KB
testcase_23	AC	2 ms; 4,348 KB
testcase_24	AC	2 ms; 4,348 KB
testcase_25	AC	2 ms; 4,348 KB
testcase_26	AC	2 ms; 4,348 KB
testcase_27	AC	2 ms; 4,348 KB
testcase_28	AC	1 ms; 4,348 KB

ソースコード

#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;


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()
{
	// input
	ll n;
	cin >> n;
	vector<ll> a(n);
	rep(i, n)cin >> a[i];

	// seg init
	auto f = [](ll l, ll r) {return l + r; };
	auto g = [](ll data, ll lazy, int siz) {return lazy; };
	auto h = [](ll lazy, ll query) {return query; };
	LazySegmentTree<ll> seg(n, f, g, h, 0, 0);

	// mapper
	map<ll, set<ll>> mp;
	rep(i, n)mp[a[i]].insert(i);

	// query
	for (auto itr : mp) {
		ll val = itr.first;
		ll l = *itr.second.begin();
		ll r = *(--itr.second.end());
		seg.update(l, r + 1, val);
	}
	rep(i, n)cout << seg[i] << " ";
	cout << endl;
	return 0;
}