제출 #924630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924630		esomer	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	345 ms	37876 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int getCol(int x, vector<int>& leader, vector<int>& A, vector<int>& col){
	if(col[x] != -1) return col[x];
	if(leader[x] == -1){
		col[x] = A[x];
	}else{
		col[x] = getCol(leader[x], leader, A, col);
	}
	return col[x];
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	vector<int> A(N);
	for(auto &i : A) cin >> i;
	vector<int> leader(N, -1);
	set<int> left;
	map<int, vector<int>> hv;
	for(int i = N-1; i >= 0; i--){
		hv[A[i]].push_back(i);
	}
	for(int i = 0; i < N; i++){
		if(hv[A[i]].back() != i){
			int j = hv[A[i]].back();
			auto it = left.lower_bound(j);
			while(it != left.end()){
				leader[*it] = i;
				hv[A[*it]].pop_back();
				left.erase(it);
				it = left.lower_bound(j);
			}
		}
		left.insert(i);
	}
	vector<int> col(N, -1);
	for(int i = 0; i < N; i++){
		cout << getCol(i, leader, A, col) << "\n";
	}
}

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