Cod sursa(job #2266663)

Utilizator retrogradLucian Bicsi retrograd Data 22 octombrie 2018 20:22:10
Problema Subsir 2 Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <bits/stdc++.h>

using namespace std;

int main() {
    ifstream cin("subsir2.in");
    ofstream cout("subsir2.out");

    int n; cin >> n;
    vector<int> v(n), stk, nxt(n), len(n + 1, 0), cnt(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    
    for (int i = n - 1; i >= 0; --i) {
        while (stk.size() && v[stk.back()] < v[i])
            stk.pop_back();
        nxt[i] = stk.size() ? stk.back() : n;
        len[i] = 1 + len[nxt[i]];
        cnt[len[i]] += 1;
        stk.push_back(i);
    }

    int at = 0;
    auto adv = [&]() { --cnt[len[at++]]; };
    
    cout << len[0] << endl;
    for (int l = len[0]; l > 0; --l) {
        while (cnt[l] > 0) adv();
        int choose = at - 1;
        cout << choose + 1 << " ";
        while (at < nxt[choose]) adv();
    }

    return 0;
}