結果

問題 No.318 学学学学学
ユーザー airisairis
提出日時 2015-12-12 01:48:05
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 258 ms / 2,000 ms
コード長 2,490 bytes
コンパイル時間 1,157 ms
コンパイル使用メモリ 93,916 KB
実行使用メモリ 27,492 KB
最終ジャッジ日時 2023-09-04 17:48:22
合計ジャッジ時間 5,366 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 19 ms
12,964 KB
testcase_01 AC 36 ms
14,552 KB
testcase_02 AC 45 ms
14,892 KB
testcase_03 AC 30 ms
13,828 KB
testcase_04 AC 39 ms
14,516 KB
testcase_05 AC 258 ms
27,492 KB
testcase_06 AC 190 ms
19,468 KB
testcase_07 AC 158 ms
16,948 KB
testcase_08 AC 133 ms
15,676 KB
testcase_09 AC 113 ms
14,116 KB
testcase_10 AC 85 ms
12,512 KB
testcase_11 AC 249 ms
27,288 KB
testcase_12 AC 160 ms
19,464 KB
testcase_13 AC 130 ms
17,104 KB
testcase_14 AC 109 ms
15,092 KB
testcase_15 AC 93 ms
13,684 KB
testcase_16 AC 71 ms
12,360 KB
testcase_17 AC 137 ms
19,676 KB
testcase_18 AC 118 ms
19,468 KB
testcase_19 AC 138 ms
19,468 KB
testcase_20 AC 55 ms
12,620 KB
testcase_21 AC 5 ms
11,612 KB
testcase_22 AC 5 ms
11,700 KB
testcase_23 AC 5 ms
11,656 KB
testcase_24 AC 5 ms
11,612 KB
testcase_25 AC 5 ms
11,716 KB
testcase_26 AC 5 ms
11,668 KB
testcase_27 AC 5 ms
11,708 KB
testcase_28 AC 4 ms
11,656 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;

int N;
int a[100005];

map<int, vector<int> > pool;
set<int> keys;

struct LazyPropagationSegmentTree {
	int n;
	ll lazy[500005];
	ll  dat[500005];
	void init(int m) {
		n = 1;
		while (n < m) n *= 2;
		memset(lazy, 0, sizeof(lazy));
		memset(dat, 0, sizeof(dat));
	}
	void lazy_evaluate(int k, int l, int r) {
		dat[k] = lazy[k];
		if (k < n - 1) {
			lazy[2 * k + 1] = lazy[k];
			lazy[2 * k + 2] = lazy[k];
		}
		lazy[k] = 0;
	}
	void paint(int a, int b, int x, int k, int l, int r) {
		if (lazy[k] != 0) {
			lazy_evaluate(k, l, r);
		}
		if (b <= l || r <= a) return;
		if (a <= l && r <= b) {
			dat[k] = 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;
		paint(a, b, x, chl, l, m);
		paint(a, b, x, chr, m, r);
	}
	ll query(int a, int b, int k, int l, int r) {
		if (lazy[k] != 0) {
			lazy_evaluate(k, l, r);
		}
		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);
	}
};

LazyPropagationSegmentTree seg;



void solve() {
	seg.init(N);
	rep(i, N) {
		keys.insert(a[i]);
		pool[a[i]].push_back(i);
	}
#if 0
	foreach(itr, pool) {
		printf("%d: ", itr->first);
		rep(i, itr->second.size()) {
			printf("%d,", itr->second[i]);
		}
		printf("\n");
	}
#endif
	foreach(itr, keys) {
		int key = *itr;
		sort(pool[key].begin(), pool[key].end());
		int left = pool[key][0];
		int right = pool[key].back();
		seg.paint(left, right+1, key, 0, 0, seg.n);
	}
	for (int i = 0; i < N; i++) {
		printf("%d%c", seg.query(i, i+1, 0, 0, seg.n), i == N-1 ? '\n' : ' ');
	}
}


int main() {
	cin >> N;
	rep(i, N) cin >> a[i];
	solve();
	return 0;
}
0