제출 #1263423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263423		kustov_vadim_533	Stone Arranging 2 (JOI23_ho_t1)	C++20	100 / 100	134 ms	140100 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define len(v) (int)((v).size())

template<typename T>
ostream& operator<<(ostream& out, const vector<T> &a){
	for  (auto& x : a){
		out << x << ' ';
	}
	out << '\n';
	return out;
}

template<typename T>
istream& operator>>(istream& in, vector<T> &a){
	for (size_t i = 0; i < a.size(); ++i){
		in >> a[i];
	}
	return in;
}

mt19937 gen;

inline void solve() {
	int n;
	cin >> n;

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

	vector<int> b = a;
	sort(b.begin(), b.end());
	b.resize(unique(b.begin(), b.end()) - b.begin());

	for (int i = 0; i < n; ++i){
		a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
	}

	vector<stack<int>> c(n);
	stack<int> st;

	for (int i = 0; i < n; ++i){
		if (!c[a[i]].empty()){
			while (st.top() > c[a[i]].top()){
				c[a[st.top()]].pop();
				st.pop();
			}
		}

		c[a[i]].push(i);
		st.push(i);
	}

	int cur = -1;
	for (int i = n - 1; i >= 0; --i){
		if (!st.empty() && st.top() == i) {
			cur = a[i];
			st.pop();
		}
		a[i] = cur;
	}

	for (int i = 0; i < n; ++i){
		cout << b[a[i]] << '\n';
	}
	cout << '\n';
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(60);

	int t = 1;
//	cin >> t;

	while (t--) {
		solve();
	}
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40