Submission #780869

#TimeUsernameProblemLanguageResultExecution timeMemory
780869boris_mihovStone Arranging 2 (JOI23_ho_t1)C++17
100 / 100
133 ms16724 KiB
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 200000 + 10;
const int INF  = 1e9;

int n;
int a[MAXN];
std::set <int> wasThere;
std::vector <std::pair <int,int>> st;
std::stack <int> output;

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        if (!wasThere.count(a[i]))
        {
            wasThere.insert(a[i]);
            st.push_back({i, a[i]});
        } else
        {
            while (st.back().second != a[i])
            {
                wasThere.erase(wasThere.find(st.back().second));
                st.pop_back();
            }
        }
    }
    
    int ptr = n;
    while (!st.empty())
    {
        while (ptr >= st.back().first)
        {
            output.push(st.back().second);
            ptr--;
        }
    
        st.pop_back();
    }

    while (!output.empty())
    {
        std::cout << output.top() << '\n';
        output.pop();
    }
}

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

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...