#976719 (C++23) No.318 学学学学学

• 問題: No.318 学学学学学
• ユーザー: 赤信号
• 提出日時: 2024-04-22 17:59:54
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 196 ms / 2,000 ms
• コード長: 3,927 bytes
• コンパイル時間: 4,908 ms
• コンパイル使用メモリ: 308,388 KB
• 実行使用メモリ: 16,896 KB
• 最終ジャッジ日時: 2024-04-22 18:00:03
• 合計ジャッジ時間: 8,405 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	13 ms; 5,248 KB
testcase_01	AC	28 ms; 5,888 KB
testcase_02	AC	33 ms; 6,144 KB
testcase_03	AC	20 ms; 5,376 KB
testcase_04	AC	27 ms; 6,144 KB
testcase_05	AC	182 ms; 16,896 KB
testcase_06	AC	151 ms; 13,696 KB
testcase_07	AC	146 ms; 12,672 KB
testcase_08	AC	110 ms; 11,776 KB
testcase_09	AC	102 ms; 11,264 KB
testcase_10	AC	84 ms; 10,752 KB
testcase_11	AC	196 ms; 16,896 KB
testcase_12	AC	129 ms; 13,696 KB
testcase_13	AC	111 ms; 12,672 KB
testcase_14	AC	94 ms; 11,904 KB
testcase_15	AC	84 ms; 11,264 KB
testcase_16	AC	56 ms; 10,752 KB
testcase_17	AC	132 ms; 13,824 KB
testcase_18	AC	113 ms; 13,824 KB
testcase_19	AC	129 ms; 13,696 KB
testcase_20	AC	54 ms; 10,624 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	2 ms; 5,376 KB
testcase_23	AC	2 ms; 5,376 KB
testcase_24	AC	1 ms; 5,376 KB
testcase_25	AC	2 ms; 5,376 KB
testcase_26	AC	2 ms; 5,376 KB
testcase_27	AC	2 ms; 5,376 KB
testcase_28	AC	2 ms; 5,376 KB

ソースコード

#pragma GCC optimize("O3")

#ifdef LOCAL
#include "algo/debug_ver2.hpp"
#else
#define _debug(...) 42
#endif

#include <bits/stdc++.h>

using namespace std;

template <typename T, typename U>
struct LazySegmentTree {
	int n;
	vector<T> nodes;
	vector<U> lazy;
	vector<int> sizes;
	T ti;
	U ui;
	function<T(T, T)> op;
	function<T(T, U, int)> mapping;
	function<U(U, U)> composition;

	int bit_width(int x) {
		int ret = 0;
		while (x) x >>= 1, ++ret;
		return ret;
	}

	LazySegmentTree(int size, T ti, U ui, function<T(T, T)> op, function<T(T, U, int)> mapping, function<U(U, U)> composition)
		: ti(ti), ui(ui), op(op), mapping(mapping), composition(composition) {
		n = 1;
		while (n < size) n *= 2;
		nodes.resize(n * 2, ti);
		lazy.resize(n * 2, ui);
		sizes.resize(n * 2);
		for (int i = 0; i < size; ++i) sizes[n + i] = 1;
		for (int i = n - 1; i > 0; --i) sizes[i] = sizes[i * 2] + sizes[i * 2 + 1];
	}

	LazySegmentTree(vector<T> vec, T ti, U ui, function<T(T, T)> op, function<T(T, U, int)> mapping, function<U(U, U)> composition)
		: LazySegmentTree(vec.size(), ti, ui, op, mapping, composition) {
		build(vec);
	}

	void build(vector<T> vec) {
		for (int i = 0; i < n; ++i) nodes[n + i] = vec[i];
		for (int i = n - 1; i > 0; --i) update(i);
	}

	void set(int k, T x) {
		k += n;
		for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) propagate(k >> i);
		nodes[k] = x;
		for (int i = 1; i < bit_width((unsigned int)n); ++i) update(k >> i);
	}

	T get(int k) {
		k += n;
		for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) propagate(k >> i);
		return nodes[k];
	}

	T prod(int l, int r) {
		l += n, r += n;
		for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) {
			if (((l >> i) << i) != l) propagate(l >> i);
			if (((r >> i) << i) != r) propagate((r - 1) >> i);
		}
		T l_cum = ti, r_cum = ti;
		for (; l < r; l /= 2, r /= 2) {
			if (l % 2 == 1) l_cum = op(l_cum, nodes[l++]);
			if (r % 2 == 1) r_cum = op(r_cum, nodes[--r]);
		}
		return op(l_cum, r_cum);
	}

	T all_prod() {
		return nodes[1];
	}

	void apply(int k, U x) {
		k += n;
		for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) propagate(k >> i);
		nodes[k] = mapping(nodes[k], x, sizes[k]);
		for (int i = 1; i < bit_width((unsigned int)n); ++i) update(k >> i);
	}

	void apply(int l, int r, U x) {
		l += n, r += n;
		for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) {
			if (((l >> i) << i) != l) propagate(l >> i);
			if (((r >> i) << i) != r) propagate((r - 1) >> i);
		}
		for (int l2 = l, r2 = r; l2 < r2; l2 /= 2, r2 /= 2) {
			if (l2 % 2 == 1) all_apply(l2++, x);
			if (r2 % 2 == 1) all_apply(--r2, x);
		}
		for (int i = 1; i < bit_width((unsigned int)n); ++i) {
			if (((l >> i) << i) != l) update(l >> i);
			if (((r >> i) << i) != r) update((r - 1) >> i);
		}
	}

private:

	void update(int x) {
		nodes[x] = op(nodes[x * 2], nodes[x * 2 + 1]);
	}

	void all_apply(int i, U x) {
		nodes[i] = mapping(nodes[i], x, sizes[i]);
		if (i < n) lazy[i] = composition(lazy[i], x);
	}

	void propagate(int i) {
		all_apply(i * 2, lazy[i]);
		all_apply(i * 2 + 1, lazy[i]);
		lazy[i] = ui;
	}
};

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;

	vector<long long> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];

	map<long long, pair<int, int>> pos;
	for (int i = 0; i < n; ++i) {
		if (pos.contains(a[i])) pos[a[i]] = {min(pos[a[i]].first, i), max(pos[a[i]].second, i + 1)};
		else pos[a[i]] = {i, i + 1};
	}

	LazySegmentTree<long long, long long>
		lsgt(a, 0, INT_MIN,
			plus(),
			[](long long x, long long y, int len) { return y == INT_MIN ? x : y * len; },
			[](long long x, long long y) { return y == INT_MIN ? x : y; }
		    );

	for (map<long long, pair<int, int>>::iterator it = pos.begin(); it != pos.end(); ++it) lsgt.apply(it -> second.first, it -> second.second, it -> first);

	for (int i = 0; i < n; ++i) cout << (i == 0 ? "" : " ") << lsgt.get(i);
	cout << '\n';
}