Cod sursa(job #2931006)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 30 octombrie 2022 10:43:09
Problema Subsir crescator maximal Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.48 kb
#include<fstream>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<climits>
#include<iomanip>
#include<cstring>
#include<bitset>

#define MAX 100000

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

//ifstream f("in.in");
//ofstream g("out.out");

int aib[MAX+5];
int n;
int sol = -1;

struct vectStruct{
    int val;
    int poz;
}v[MAX+5],s[MAX+5];

bool cmp(vectStruct a,vectStruct b){
    if(a.val<b.val || (a.val == b.val && a.poz<b.poz)){
        swap(v[a.poz].poz,v[b.poz].poz);
        return 1;
    }
    return 0;
}

void update(int val,int poz){

    for(int i=poz;i<=n;i+=(i&-i)){
        aib[i]+=val;
    }
}

int query(int poz){

    int val=0;
    for(int i=poz;i>=1;i-=(i&-i)){
        val+=aib[i];
    }
    return val;
}

int main(){

    f>>n;
    for(int i=1;i<=n;i++){
        f>>v[i].val;
        v[i].poz = i;

        s[i].val = v[i].val;
        s[i].poz = i;
    }

    sort(s+1,s+n+1,cmp);

    /*for(int i=1;i<=n;i++){
        cout<<v[i].val<<" "<<v[i].poz<<'\n';
    }

    cout<<"================="<<'\n';

    for(int i=1;i<=n;i++){
        cout<<s[i].val<<" "<<s[i].poz<<'\n';
    }

    cout<<"================="<<'\n';
    cout<<"================="<<'\n';*/

    ///fix
    int lastDif = 1;
    for(int i=2;i<=n;i++){

        while(s[i].val == s[lastDif].val && i<=n){

            v[s[i].poz].poz = v[s[lastDif].poz].poz;

            i++;
        }
        lastDif = i;
    }


    /*for(int i=1;i<=n;i++){
        cout<<v[i].val<<" "<<v[i].poz<<'\n';
    }

    cout<<"================="<<'\n';

    for(int i=1;i<=n;i++){
        cout<<s[i].val<<" "<<s[i].poz<<'\n';
    }*/

    ///find max
    for(int i=1;i<=n;i++){
        sol = max(sol,query(v[i].poz-1)+1);

        if((query(v[i].poz)-query(v[i].poz-1))==0){
            update(1,v[i].poz);
        }
    }
    g<<sol<<'\n';

    ///reset
    for(int i=1;i<=n;i++){
        aib[i] = 0;
    }

    ///print sequence
    for(int i=1;i<=n;i++){
        if(query(v[i].poz-1)+1 == sol){

            for(int j=1;j<v[i].poz;j++){
                if((query(j)-query(j-1))==1){
                    g<<s[j].val<<" ";
                }
            }
            g<<v[i].val;

            i=n+1;
            break;
        }

        if((query(v[i].poz)-query(v[i].poz-1))==0){
            update(1,v[i].poz);
        }
    }

    f.close();
    g.close();
    return 0;
}