제출 #774764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
774764		vjudge1	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	576 ms	34404 KiB

Main

#include<bits/stdc++.h>

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

using namespace std;

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

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 i = 1; i <= n; ++i) {
        if (val.count(a[i]) == 0) {
            reverse(pos[a[i]].begin(), pos[a[i]].end());
            val[a[i]] = 1;
        }
    }


    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: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40