Untitled
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