Submission #773813

#	Time	Username	Problem	Language	Result	Execution time	Memory
773813		n3rm1n	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	63 ms	17520 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 2e5 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, a[MAXN];
void read()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i)
        cin >> a[i];
}
unordered_map < int, int > mp;
void solve()
{
    stack < pair <int, int> > s;
    for (int i = 1; i <= n; ++ i)
    {
        if(mp[a[i]] == 0)
        {
            mp[a[i]] ++;
            s.push(make_pair(a[i], 1));
        }
        else
        {
            int cnt = 0;
            while(s.top().first != a[i])
            {
                cnt += s.top().second;
                mp[s.top().first] -= s.top().second;
                s.pop();
            }
            cnt += s.top().second;
            s.pop();
            s.push(make_pair(a[i], cnt+1));
            mp[a[i]] = cnt+1;
        }
    }
    vector < int > v;
    while(!s.empty())
    {
        int x = s.top().first, y = s.top().second;
        while(y --)
        {
            v.push_back(x);
        }
        s.pop();
    }
    for (int i = v.size()-1; i >= 0; -- i)
        cout << v[i] << endl;
}
int main()
{
    speed();

    read();
    solve();
    return 0;
}

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