Submission #924145

#	Time	Username	Problem	Language	Result	Execution time	Memory
924145		adhityamv	Stone Arranging 2 (JOI23_ho_t1)	C++17	35 / 100	27 ms	5220 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
int INF=1000000000;
void solve(){
    int n;
    cin >>n;
    int a[n];
    for(int i=0;i<n;i++) cin >> a[i];
    set<int> allvals;
    map<int,int> index;
    int ind=0;
    vector<int> val;
    for(int i=0;i<n;i++){
        if(allvals.find(a[i])==allvals.end()){
            val.push_back(a[i]);
            index[a[i]]=ind;
            ind++;
            allvals.insert(a[i]);
        }
    }
    int b[n];
    for(int i=0;i<n;i++) b[i]=index[a[i]];
    stack<pii> ans;
    int nind[n];
    for(int i=0;i<n;i++) nind[i]=b[i];
    int oind[n];
    for(int i=0;i<n;i++) oind[nind[i]]=nind[i];
    for(int i=0;i<n;i++){
        if(!ans.empty() && nind[i]>ans.top().first){
            oind[ans.top().first+1]=oind[nind[i]];
            nind[i]=ans.top().first+1;
        }
        while(!ans.empty() && ans.top().first>=nind[i]){
            ans.pop();
        }
        ans.push(mp(nind[i],i));
    }
    int fans[n];
    ind=n-1;
    int pv=-1;
    while(!ans.empty()){
        auto p=ans.top();
        ans.pop();
        while(ind>p.second){
            fans[ind]=val[oind[pv]];
            ind--;
        }
        pv=p.first;
    }
    while(ind>=0){
        fans[ind]=val[oind[pv]];
        ind--;
    }
    for(int i=0;i<n;i++) cout << fans[i] << "\n";
}
signed main(){
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    t=1;
    //cin >> t;
    while(t--) solve();
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

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