fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define pii pair<int,int>
  13. #define pil pair<int,ll>
  14. #define pli pair<ll,int>
  15. #define MOD 1000000007
  16. #define el "\n"
  17. #define MAX 200005
  18.  
  19. int n,a[MAX],f[MAX],bit[MAX];
  20. vector<int> b;
  21.  
  22. void pre()
  23. {
  24.     foru(i,1,n) b.pb(a[i]);
  25.     sort(b.begin(),b.end());
  26.     b.erase(unique(b.begin(),b.end()),b.end());
  27.     foru(i,1,n) a[i]=lower_bound(b.begin(),b.end(),a[i])-b.begin()+1;
  28. }
  29.  
  30. void update(int pos, int val)
  31. {
  32.     for(;pos<=n;pos+=(pos&(-pos))) bit[pos]=max(bit[pos],val);
  33. }
  34.  
  35. int query(int pos)
  36. {
  37.     int ans=0;
  38.     for(;pos>=1;pos-=(pos&(-pos))) ans=max(ans,bit[pos]);
  39.     return ans;
  40. }
  41.  
  42. void calc()
  43. {
  44.     int ans=1;
  45.     foru(i,1,n)
  46.     {
  47.         f[i]=1;
  48.         int q=query(a[i]-1);
  49.         f[i]+=q;
  50.         update(a[i],f[i]);
  51.     }
  52.     memset(bit,0,sizeof(bit));
  53.     ford(i,n,1)
  54.     {
  55.         int cur=1;
  56.         int q=query(a[i]-1);
  57.         cur+=q;
  58.         update(a[i],cur);
  59.         ans=max(ans,f[i]+cur-1);
  60.     }
  61.     cout<<ans;
  62. }
  63.  
  64. int main()
  65. {
  66.     fastio
  67.     #ifndef ONLINE_JUDGE
  68.     freopen(FILE ".inp","r",stdin);
  69.     freopen(FILE ".out","w",stdout);
  70.     #endif // ONLINE_JUDGE
  71.  
  72.     cin>>n;
  73.     foru(i,1,n)cin>>a[i];
  74.     pre();
  75.     calc();
  76.  
  77.     return 0;
  78. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/2yFhCb
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!