Untitled

 avatar
unknown
plain_text
a month ago
950 B
5
Indexable
#include <bits/stdc++.h>
using namespace std;

#define maxn 100005
#define treesize 2*maxn

struct pii{
    int vitri,giatri,dodai;
    friend bool operator>(pii a, pii b){
        if (a.dodai!=b.dodai) return a.dodai>b.dodai;
        return a.giatri>b.giatri;
    }
};

pii tree[treesize];

void update(int vitri,pii giatri){
    for(;vitri<treesize;vitri+=vitri&-vitri) tree[vitri]=max(tree[vitri],giatri);
}

pii query(int vitri){
    pii res{INT_MIN,INT_MIN};
    for (;vitri>0;vitri-=vitri&-vitri) res=max(res,tree[vitri]);
}

int n,a[maxn];
int trace[maxn];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if (fopen("i.txt","r")){freopen("i.txt","r",stdin);freopen("o.txt","w",stdout);}

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for (int i=1;i<=n;i++){
        pii best=query(a[i]);
        update(i+1,{best.dodai+1,a[i]});
    }

    cout<<query(n).dodai;
}
Editor is loading...
Leave a Comment