Cod sursa(job #2930898)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 29 octombrie 2022 19:42:26
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.12 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){
        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';
    }*/

    ///find max
    for(int i=1;i<=n;i++){
        if(v[i].val != v[s[v[i].poz-1].poz].val){
            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(v[i].val != v[s[v[i].poz-1].poz].val){
            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;
}