結果

問題 No.318 学学学学学
ユーザー kurenai3110kurenai3110
提出日時 2016-09-02 04:35:28
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 225 ms / 2,000 ms
コード長 3,728 bytes
コンパイル時間 1,005 ms
コンパイル使用メモリ 82,988 KB
実行使用メモリ 17,120 KB
最終ジャッジ日時 2023-09-04 20:21:54
合計ジャッジ時間 5,188 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 14 ms
4,384 KB
testcase_01 AC 31 ms
5,948 KB
testcase_02 AC 38 ms
6,232 KB
testcase_03 AC 23 ms
4,940 KB
testcase_04 AC 33 ms
6,032 KB
testcase_05 AC 225 ms
17,060 KB
testcase_06 AC 181 ms
12,304 KB
testcase_07 AC 149 ms
10,716 KB
testcase_08 AC 123 ms
9,432 KB
testcase_09 AC 103 ms
8,624 KB
testcase_10 AC 80 ms
7,592 KB
testcase_11 AC 225 ms
17,120 KB
testcase_12 AC 147 ms
12,300 KB
testcase_13 AC 125 ms
10,780 KB
testcase_14 AC 103 ms
9,456 KB
testcase_15 AC 90 ms
8,652 KB
testcase_16 AC 69 ms
7,784 KB
testcase_17 AC 118 ms
12,368 KB
testcase_18 AC 100 ms
12,408 KB
testcase_19 AC 119 ms
12,304 KB
testcase_20 AC 66 ms
7,876 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 2 ms
4,380 KB
testcase_25 AC 1 ms
4,384 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 2 ms
4,380 KB
testcase_28 AC 1 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;

#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)

struct ST {
	vector<ll> seg, lazy;   //seg木と遅延
	int size;

	ST(int n) {
		//seg木のサイズは(nが入るような２のべき乗のサイズ)*2
		size = 1;
		while (size < n) size *= 2;
		seg.resize(size * 2);
		lazy.resize(size * 2, -1);  //-1で初期化
	}

	//遅延評価
	void push(int k, int l, int r) {
		if (lazy[k] != -1) {    //遅延があるなら
								//ノードkは対応する区間の葉の総和
			seg[k] = lazy[k] * (r - l);     //ノードkを更新
											//区間[l,r)がすべてlazy[k](=v)になるから
			if (r - l > 1) {    //子ノードがあるなら
				lazy[k * 2 + 1] = lazy[k];  //ノードkの子(左)に伝搬
				lazy[k * 2 + 2] = lazy[k];  //ノードkの子(右)に伝搬
			}
			lazy[k] = -1;                   //ノードkは伝搬し終わった
		}
	}

	//x+y
	ll merge(ll x, ll y) {
		return x + y;
	}

	//[a,b)をvに
	//[l,r)はノードが持つ区間
	void update(int a, int b, ll v, int k, int l, int r) {
		//ノードkに対して遅延があるかもしれない
		//その時ノードkは更新される
		push(k, l, r);

		if (r <= a || b <= l) return;   //[a,b)がノードkの区間[l,r)と交差しない
		if (a <= l && r <= b) {         //[a,b)がノードkを完全に含む
			lazy[k] = v;    //ノードkの区間[l,r)はすべてvになったという情報
			push(k, l, r);  //子に伝搬
							//ノードkを更新
		}
		else {                        //その他
									  //左の子をupdate
			update(a, b, v, k * 2 + 1, l, (l + r) / 2);
			//右の子をupdate
			update(a, b, v, k * 2 + 2, (l + r) / 2, r);

			seg[k] = merge(seg[k * 2 + 1], seg[k * 2 + 2]); //ノードkを更新
		}
	}

	void update(int a, int b, ll v) {
		update(a, b, v, 0, 0, size);
	}

	//[a,b)の総和
	//[l,r)はノードが持つ区間
	ll query(int a, int b, int k, int l, int r) {
		//ノードkに対して遅延があるかもしれない
		//その時ノードkは更新される
		push(k, l, r);

		if (r <= a || b <= l) return 0;             //[a,b)がノードkの区間[l,r)と交差しない時0を返す
		if (a <= l && r <= b) return seg[k];        //[a,b)がノードkを完全に含む時そのノードの値を返す
													//左の子の総和
		ll x = query(a, b, k * 2 + 1, l, (l + r) / 2);
		//右の子の総和
		ll y = query(a, b, k * 2 + 2, (l + r) / 2, r);

		return merge(x, y);//子の和を返す
	}

	ll query(int a, int b) {
		return query(a, b, 0, 0, size);
	}
};

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) scanf("%d", &a[i]);

	map<int, int> first, last;

	//a[i]が初めて出てくる位置i
	repr(i, n) first[a[i]] = i;    //逆rep
								   //a[i]が最後に出てくる位置i
	rep(i, n) last[a[i]] = i;

	ST st(n);
	rep(i, n) st.update(i, i + 1, a[i]);   //seg木初期化

										   //mapを回すときのfor文
										   //kvがmap(first)になって順番に処理されていく(mapはキーでsortされているのでその順番(要するに小さい順))
										   //firstはキー(a[i]),secondは値(i)
										   //小さい数字から順番にその数字が出てくる最初と最後の間の範囲をその数字に更新
	for (auto kv : first) {
		//if (last.count(kv.first)) { //map::count(x) キーxがあるかないか （これ必要なのか？） 
			st.update(kv.second, last[kv.first] + 1, kv.first); //区間[first(=i),last+1)をa[i]に
		//}
	}

	rep(i, n) printf("%d ", (int)st.query(i, i + 1));  //区間[i,i+1)の値、要するにiの値
	cout << endl;

	return 0;
}
0