제출 #959074

#제출 시각아이디문제언어결과실행 시간메모리
959074Younis_DwaiGlobal Warming (CEOI18_glo)C++14
10 / 100
174 ms18472 KiB
#include <bits/stdc++.h> //#define int long long #define F first #define S second #define pb push_back #define in insert #define mid (l+r)/2 #define endl "\n" //#define pop pop_back using namespace std ; int n,x,tree[8000009],b[200009],res=0,dp[200009],c[200009]; int query(int node , int l , int r , int s , int e){ if(l>=s && r<=e) return tree[node]; else if(l>e || r<s) return 0; return max(query(node*2,l,mid,s,e),query(node*2+1,mid+1,r,s,e)); } void upd(int node , int l , int r , int id , int v){ if(l==r){ tree[node]=v; return ; } else if(id<=mid) upd(node*2,l,mid,id,v); else upd(node*2+1,mid+1,r,id,v); tree[node]=max(tree[node*2],tree[node*2+1]); return ; } int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); cin>>n>>x; vector<int> v; for(int i=1;i<=n;i++){ cin>>b[i]; v.pb(b[i]); } sort(begin(v),end(v));v.resize(unique(v.begin(),v.end())-v.begin()); map<int,int> mp;int t=0;for(auto u : v) mp[u]=++t; for(int i=1;i<=n;i++) b[i]=mp[b[i]]; for(int i=1;i<=n;i++){ dp[i]=1+query(1,0,n,0,b[i]-1); res=max(res,dp[i]); upd(1,0,n,b[i],dp[i]); } cout<<res; return 0; }
#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...