제출 #924145

#제출 시각아이디문제언어결과실행 시간메모리
924145adhityamvStone Arranging 2 (JOI23_ho_t1)C++17
35 / 100
27 ms5220 KiB
#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"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...