Submission #762892

#	Time	Username	Problem	Language	Result	Execution time	Memory
762892		caganyanmaz	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	120 ms	8132 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int main()
{
        int n;
        cin >> n;
        vector<int> v(n);
        for (int& i : v) cin >> i;
        vector<int> compress = v;
        sort(compress.begin(), compress.end());
        for (int& i : v)
                i = lower_bound(compress.begin(), compress.end(), i) - compress.begin();
        vector<int> nxt(n, -1), last(n, -1), res(n);
        for (int i = n-1; i >= 0; i--)
        {
                if (last[v[i]] == -1)
                        last[v[i]] = i;
                else
                        nxt[i] = last[v[i]];
        }
        for (int i = 0; i < n; i++)
        {
                if (nxt[i] != -1)
                {
                        int j = nxt[i];
                        while (i < j) res[i++] = compress[v[j]];
                        res[i] = compress[v[j]];
                }
                else
                        res[i] = compress[v[i]];
        }
        for (int i : res)
                cout << i << "\n";
}

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