Cod sursa(job #2467685)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 4 octombrie 2019 20:34:37
Problema Subsir 2 Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5005;

int v[MAXN], arb[4 * MAXN];
vector<int> ans;
int n;

int query(int nod, int st, int dr, int a, int b){
    if(a <= st && dr <= b) return arb[nod];
    int mij = (st + dr) / 2, leftans = n + 1, rightans = n + 1;
    if(a <= mij) leftans = query(2 * nod, st, mij, a, b);
    if(b > mij) rightans = query(2 * nod + 1, mij + 1, dr, a, b);
    if(v[leftans] < v[rightans]) return leftans;
    else return rightans;
}

void update(int nod, int st, int dr, int a, int b){
    if(st == dr && st == a){
        arb[nod] = b;
        return;
    }
    int mij = (st + dr) / 2;
    if(a <= mij) update(2 * nod, st, mij, a, b);
    else update(2 * nod + 1, mij + 1, dr, a, b);
    if(v[arb[2 * nod]] < v[arb[2 * nod + 1]]) arb[nod] = arb[2 * nod];
    else arb[nod] = arb[2 * nod + 1];
}

void lookscm(int nod, int st, int dr){
    if(st >= dr) return;
    while(v[arb[nod]] <= v[ans.back()]){
        nod = 2 * nod + 1;
        int mij = (st + dr) / 2;
        st = mij + 1;
    }
    ans.push_back(arb[nod]);
    lookscm(nod, st, dr);
}

int main()
{
    ifstream fin("subsir2.in");
    ofstream fout("subsir2.out");
    fin >> n;
    for(int i = 1; i <= 4 * n; ++i) arb[i] = n + 1;
    v[n + 1] = 1e9;
    for(int i = 1; i <= n; ++i){
        fin >> v[i];
        update(1, 1, n, i, i);
    }
    ans.push_back(0);
    lookscm(1, 1, n);
    ans.erase(ans.begin());
    fout << ans.size() << "\n";
    for(auto x:ans) fout << x << " ";
    return 0;
}