Submission #774742

#	Time	Username	Problem	Language	Result	Execution time	Memory
774742		vjudge1	Stone Arranging 2 (JOI23_ho_t1)	C++17	35 / 100	30 ms	9940 KiB

Main

#include<bits/stdc++.h>

#define sz(a) (int)a.size()
#define MaxN 200005

using namespace std;

int n, a[MaxN];
vector<int> pos[MaxN];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);


    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];


    for(int i = 1; i <= n; ++i) pos[a[i]].push_back(i);
    for(int c = 1; c <= n; ++c) reverse(pos[c].begin(), pos[c].end());


    int p = 1;
    while(p < n) { // a[n] = a[n]
        int nxt = -1;
        while(sz(pos[a[p]]) > 0) {
            nxt = pos[a[p]][sz(pos[a[p]])-1];
            if (p >= nxt) {
                pos[a[p]].pop_back();
                nxt = -1;
            }
            else {
                break;
            }
        }
        if (nxt != -1) {
            for(int i = p+1; i <= nxt; ++i) a[i] = a[p];
            p = nxt;
        }
        else {
            ++p;
        }
    }


    for(int i = 1; i <= n; ++i) cout << a[i] << "\n";


    return 0;
}

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