Submission #774683

#	Time	Username	Problem	Language	Result	Execution time	Memory
774683		vjudge1	Stone Arranging 2 (JOI23_ho_t1)	C++17	60 / 100	2085 ms	111560 KiB

Main

#include<bits/stdc++.h>
#define fn(n) for(int i=1; i<=n; i++)
#pragma GCC optimize("O3")

using namespace std;
using ll=long long;

int n;
int a[200002];
map<int, vector<int>> pos;

void nhap(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
}

void solve(){
    for(int i=1; i<=n; i++){
    	if(pos[a[i]].size()!=0){
    		stack<int> s;
    		for(int j=i-1; j>pos[a[i]].back(); j--){
	            if(pos[a[j]].size() && j==pos[a[j]].back()){
	            	pos[a[j]].pop_back();
	            }
	            a[j]=a[i];
	            s.push(j);
	        }
	        while(!s.empty()){
	        	pos[a[i]].push_back(s.top());
	        	s.pop();
	        }
    	}
        pos[a[i]].push_back(i);
    }
    for(int i=1; i<=n; i++){
        cout << a[i] << '\n';
    }
    cout << '\n';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    nhap();
    solve();
}

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