fork(5) download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. #define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
  7. #define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
  8. #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
  9. #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
  10. #define X first
  11. #define Y second
  12. using namespace std;
  13. int n, a[100010], f[100010], k = 0, lst[100010];
  14.  
  15. int Find(int p) {
  16.     int l = 1, r = k, m = (l+r)>>1;
  17.     while (l!=m && r!=m) {
  18.         if (a[lst[m]] < a[p]) l = m;
  19.         else r = m-1;
  20.         m = (l+r)>>1;
  21.     }
  22.     REPD(i,r,l) if (a[lst[i]] < a[p]) return i;
  23.     return 0;
  24. }
  25. int Find2(int p) {
  26.     int l = 1, r = k, m = (l+r)>>1;
  27.     while (l!=m && r!=m) {
  28.         if (a[lst[m]] > a[p]) l = m;
  29.         else r = m-1;
  30.         m = (l+r)>>1;
  31.     }
  32.     REPD(i,r,l) if (a[lst[i]] > a[p]) return i;
  33.     return 0;
  34. }
  35. void process() {
  36.     scanf("%d",&n);
  37.     REP(i,1,n) scanf("%d",&a[i]);
  38.     int ans = 0, t;
  39.     REPD(i,n,1) {
  40.         t = Find(i);
  41.         f[i] = t+1;
  42.         if (t+1 > k) {
  43.             k++; lst[k] = i;
  44.         }
  45.         else if (a[i] < a[lst[t+1]]) lst[t+1] = i;
  46.     }
  47.     k = 0;
  48.     REPD(i,n,1) {
  49.         t = Find2(i);
  50.         ans = max(ans,f[i]+t);
  51.         if (t+1 > k) {
  52.             k++; lst[k] = i;
  53.         }
  54.         else if (a[i] > a[lst[t+1]]) lst[t+1] = i;
  55.     }
  56.     cout << ans;
  57. }
  58. int main(void)
  59. {
  60.     process();
  61. 	return 0;
  62. }
  63.  
  64.  
Success #stdin #stdout 0s 4316KB
comments (?)
stdin
copy 
5
3 3 5 4 1
stdout
copy 
3
https://ideone.com/kkrdIF
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!