Submission #780869

#	Time	Username	Problem	Language	Result	Execution time	Memory
780869		boris_mihov	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	133 ms	16724 KiB

Main

#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;
}

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