Submission #1158823

#TimeUsernameProblemLanguageResultExecution timeMemory
1158823the_ZHERStone Arranging 2 (JOI23_ho_t1)C++20
100 / 100
60 ms21352 KiB
#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
const int inf=1e17;
const int N=1e5+5;
const int N1=1e5+5;
const int N2=5e6+6;
const int mod=1e9+7;
const int k1=447;
struct edge{
    int d,in;
};
struct edge1{
    int x,y,c;
};
vector<int>v;
map<int,int>mp;
unordered_map<int,int> dp;
vector<pair<int,int> >v1;
signed main(){
boost;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        v.push_back(x);
    }
    stack<pair<int,int> >st;
    for(int i=0;i<n;i++){
        if(dp[v[i]]==0){
            dp[v[i]]++;
            st.push({v[i],1ll});
        }else{
            int cnt=0;
            while(st.top().first!=v[i]){
                dp[st.top().first]-=st.top().second;
                cnt+=st.top().second;
                st.pop();
            }
            st.top().second+=cnt+1;
            dp[v[i]]+=cnt+1;
        }
    }
    while(st.size()>0){
        v1.push_back(st.top());
        st.pop();
    }
    reverse(v1.begin(),v1.end());
    for(int i=0;i<v1.size();i++){
        for(int j=0;j<v1[i].second;j++){
            cout<<v1[i].first<<"\n";
        }
    }
}  
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...