Cod sursa(job #3168247)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 11 noiembrie 2023 20:08:34
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.46 kb
#include<bits/stdc++.h>
#define DIM 100001

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int dp[DIM], v[DIM], freq[DIM];

int wmt[4 * DIM];

int n, i, answer, f;

map <int, vector <int>> mp;

map <int, bool> ok;

map <int, bool> :: iterator it;

unordered_map <int, int> nanswer, reverse_answer;

stack <int> st;

void solve(int val, int pos){

    st.push(reverse_answer[v[pos]]);

    if(val == 1)
        return ;

    int st = 0, dr = mp[val - 1].size() - 1, target = pos - 1, sol = 0;

    while(st <= dr){

        int mij = (st + dr) >> 1;

        if(mp[val - 1][mij] <= target){

            sol = mij;

            st = mij + 1;

        }

        else dr = mij - 1;

    }

    solve(val - 1, mp[val - 1][sol]);

}

void Update(int node, int st, int dr, int a, int b){

    if(st == dr)
        wmt[node] = max(wmt[node], b);

    else {

        int mij = (st + dr) >> 1;

        if(a <= mij)
            Update(node << 1, st, mij, a, b);

        if(a > mij)
            Update(node << 1 | 1, mij + 1, dr ,a, b);

        wmt[node] = max(wmt[node << 1], wmt[node << 1 | 1]);
    }

}

int Query(int node, int st, int dr, int a, int b){

    if(dr < a || st > b)
        return 0;

    if(st >= a && dr <= b)
        return wmt[node];

    else {

        int mij = (st + dr) >> 1;

        int ok1 = Query(node << 1, st, mij, a, b);
        int ok2 = Query(node << 1 | 1, mij + 1, dr, a , b);

        return max(ok1, ok2);

    }


}

int main(){

    fin >> n;

    for(i=1;i<=n;i++){
        fin >> v[i];
        ok[v[i]] = 1;
    }

    for(it = ok.begin(); it != ok.end(); it++){

        nanswer[it -> first] = ++f;

        reverse_answer[f] = it -> first;

    }

    for(i=1;i<=n;i++)
        v[i] = nanswer[v[i]];

    for(i=1;i<=n;i++){

        if(v[i] - 1 >= 1)

            dp[i] = Query(1, 1, DIM, 1, v[i] - 1) + 1;

        else dp[i] = 1;

        Update(1, 1, DIM, v[i], dp[i]);

        mp[dp[i]].push_back(i);

    }

    for(i=1;i<=n;i++)
        if(!freq[dp[i]]){

            sort(mp[dp[i]].begin(), mp[dp[i]].end());

            freq[dp[i]] = 1;

        }

    for(i=1;i<=n;i++)
        if(dp[answer] < dp[i])
            answer = i;

    fout << dp[answer] << "\n";

    solve(dp[answer], answer);

    while(!st.empty()){

        fout << st.top() << " ";

        st.pop();

    }

}