結果

問題 No.318 学学学学学
ユーザー kurenai3110kurenai3110
提出日時 2016-09-02 04:35:28
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 185 ms / 2,000 ms
コード長 3,728 bytes
コンパイル時間 1,929 ms
コンパイル使用メモリ 77,444 KB
実行使用メモリ 17,280 KB
最終ジャッジ日時 2024-06-22 17:56:26
合計ジャッジ時間 5,794 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 13 ms
5,248 KB
testcase_01 AC 26 ms
6,144 KB
testcase_02 AC 30 ms
6,400 KB
testcase_03 AC 19 ms
5,376 KB
testcase_04 AC 26 ms
6,144 KB
testcase_05 AC 185 ms
17,152 KB
testcase_06 AC 158 ms
12,544 KB
testcase_07 AC 126 ms
11,008 KB
testcase_08 AC 104 ms
9,728 KB
testcase_09 AC 102 ms
8,960 KB
testcase_10 AC 77 ms
8,064 KB
testcase_11 AC 182 ms
17,280 KB
testcase_12 AC 129 ms
12,672 KB
testcase_13 AC 104 ms
11,008 KB
testcase_14 AC 94 ms
9,728 KB
testcase_15 AC 82 ms
8,960 KB
testcase_16 AC 61 ms
7,936 KB
testcase_17 AC 104 ms
12,544 KB
testcase_18 AC 94 ms
12,544 KB
testcase_19 AC 120 ms
12,672 KB
testcase_20 AC 65 ms
7,936 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 1 ms
5,376 KB
testcase_23 AC 1 ms
5,376 KB
testcase_24 AC 1 ms
5,376 KB
testcase_25 AC 1 ms
5,376 KB
testcase_26 AC 1 ms
5,376 KB
testcase_27 AC 1 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:94:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   94 |         rep(i, n) scanf("%d", &a[i]);
      |                   ~~~~~^~~~~~~~~~~~~

ソースコード

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のべき乗のサイズ)*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