Submission #1329646

#TimeUsernameProblemLanguageResultExecution timeMemory
1329646Valters07Stone Arranging 2 (JOI23_ho_t1)C++20
100 / 100
130 ms15084 KiB
#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define pb push_back
#define fi first
#define se second
#define en exit(0);
using namespace std;
const int N = 2e5 + 5;
const int INF = 1e9 + 5;
int a[N];
int main()
{
    fio
//    ifstream cin("in.in");
    stack<pair<int,int> > st;
    set<int> has;
    // st = {v, c} - c values equal to v
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        if(!has.count(a[i]))
            st.push({a[i], 1});
        else
        {
            int removed = 0;
            while(st.top().fi != a[i])
            {
                has.erase(st.top().fi);
                removed += st.top().se;
                st.pop();
            }
            removed += st.top().se;
            st.pop();
            st.push({a[i], removed + 1});
        }
        has.insert(a[i]);
    }
    vector<int> ans;
    while(!st.empty())
    {
        int v = st.top().fi, c = st.top().se;
        st.pop();
        while(c--)
            ans.pb(v);
    }
    reverse(ans.begin(), ans.end());
    for(auto x : ans)
        cout << x << " ";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...