Submission #988783

#TimeUsernameProblemLanguageResultExecution timeMemory
988783HienTDStone Arranging 2 (JOI23_ho_t1)C++11
100 / 100
177 ms13396 KiB
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	// 入力
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	// 各色に対して「最も右の位置」を前計算
	map<int, int> rightmost;
	for (int i = 0; i < N; i++) {
		rightmost[A[i]] = max(rightmost[A[i]], i);
	}

	// 塗っていく
	vector<int> answer(N);
	int curpos = 0;
	while (curpos != N) {
		int nextpos = rightmost[A[curpos]] + 1;
		for (int i = curpos; i < nextpos; i++) {
			answer[i] = A[curpos];
		}
		curpos = nextpos;
	}

	// 出力
	for (int i = 0; i < N; i++) {
		cout << answer[i] << '\n';
	}

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...