Submission #1096361

#TimeUsernameProblemLanguageResultExecution timeMemory
1096361talabuadoGlobal Warming (CEOI18_glo)C++14
0 / 100
104 ms15952 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define pb push_back #define int long long const int N=1e5+5; int n,k,ans,res,a[N]; int f[N]; int st[4*N]; int mod = 1e9; map <int ,int > mp; void update (int id , int l, int r ,int pos ,int val){ if(l> pos || r < pos){ return; } if (l==r){ st[id] = val; return; } int m=(l+r)/2; update(id *2 , l , m , pos , val); update (id*2 +1 , m+1 , r , pos , val); st[id] =max ( st[id*2],st[id*2 +1]); } int get(int id , int l ,int r ,int u , int v){ if ( v < l || u >r ){ return 0; } if(u<= l && r <=v){ return st[id]; } int m = (l+r)/2; return max(get(id*2 , l ,m, u ,v), get(id*2+1 , m+1 , r , u ,v)); } signed main (){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n; for(int i=1; i<=n;i++){ cin>>a[i]; mp[a[i]]=1 ; } int m=0; for(auto v : mp){ mp[v.fi]=++m; } for(int i=1 ; i<=n;i++){ a[i]= mp[a[i]]; m=max(m,a[i]); } update(1 ,1 ,n, a[1] , 1); for(int i=2 ; i<=n;i++){ // f[a[i]]=1; update( 1,1 ,n ,a[i],1); // for(int j=1 ; j<a[i] ; j++){ // f[a[i]]= max( f[a[i]] ,f[j] +1); // } int ad = get (1 ,1 ,n,1 , a[i]-1)+1; update(1,1 ,n , a[i] , ad); } cout<<get(1,1,n,1,n); // for(int i=1 ; i<=n;i++) cout<<a[i]<<' '; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...