Cod sursa(job #2267096)

Utilizator retrogradLucian Bicsi retrograd Data 23 octombrie 2018 11:22:33
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.94 kb
#include <bits/stdc++.h>

using namespace std;

struct SegmTree {
    int n;
    const tuple<int, int, int> kInf;
    
    struct Node {
        int min, min2;
        tuple<int, int, int> dp;
    };    
    vector<Node> data;

    SegmTree(int n) :
        n(n), kInf(n, n, n),
        data(4 * n, Node{n, n, kInf}) {}

    void Update(int pos, tuple<int, int, int> val) {
        update(1, 0, n - 1, pos, val);
    }
    tuple<int, int, int> Query(int pos) {
        return query(1, 0, n - 1, pos);
    }

    void push(int node, int b, int e) {
        if (b == e) return;
        data[node * 2].min = max(data[node * 2].min, data[node].min);
        data[node * 2 + 1].min = max(data[node * 2 + 1].min, data[node].min);
    }
    void pull(int node) {
        // Update the two minimums.
        int vals[5] = {
            data[node * 2].min, data[node * 2].min2,
            data[node * 2 + 1].min, data[node * 2 + 1].min2, n};
        sort(vals, vals + 5);
        unique(vals, vals + 5);
        data[node].min = vals[0];
        data[node].min2 = vals[1];
        // Update the dp.
        data[node].dp = kInf;
        if (data[node * 2].min == data[node].min)
            data[node].dp = min(data[node].dp, data[node * 2].dp);
        if (data[node * 2 + 1].min == data[node].min)
            data[node].dp = min(data[node].dp, data[node * 2 + 1].dp);
    }

    void update(int node, int b, int e, int pos, tuple<int, int, int> val) {
        push(node, b, e);

        if (b == e) {
            data[node].dp = val;
            data[node].min = -1;
        } else {
            int m = (b + e) / 2;
            if (pos <= m) update(node * 2, b, m, pos, val);
            else update(node * 2 + 1, m + 1, e, pos, val);
            pull(node);
        }
    }

    tuple<int, int, int> query(int node, int b, int e, int l) {
        push(node, b, e);

        if (e < l || data[node].min > l) return kInf;
        if (b >= l && data[node].min2 > l) {
            data[node].min = l;
            return data[node].dp;
        }
        int m = (b + e) / 2;
        auto ret = min(query(node * 2, b, m, l), 
                query(node * 2 + 1, m + 1, e, l));
        pull(node);
        return ret;
    }
    
};

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

    int n; cin >> n;
    vector<pair<int, int>> v(n);

    for (int i = 0; i < n; ++i) {
        cin >> v[i].first;
        v[i].second = i;
    }

    sort(v.begin(), v.end());

    SegmTree st(n);
    vector<int> dp(n), nxt(n);

    for (int i = n - 1; i >= 0; --i) {
        int pos = v[i].second;
        tie(dp[pos], ignore, nxt[pos]) = st.Query(pos);
        if (dp[pos] == n) dp[pos] = 0;
        ++dp[pos];
        st.Update(pos, make_tuple(dp[pos], i, pos));
    }

    vector<int> ans;
    for (int at = get<2>(st.Query(-1)); at < n; at = nxt[at])
        ans.push_back(at);
    
    cout << ans.size() << endl;
    for (auto x : ans) 
        cout << x + 1 << " ";
    cout << endl;

    return 0;
}