Advertisement
Guest User

Untitled

a guest
Jan 18th, 2017
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None | 0 0
  1. struct SegmTree {
  2.     vi t;
  3.     int sz;
  4.  
  5.     SegmTree(int n = 0) {
  6.         sz = 1;
  7.         while (sz < n) sz *= 2;
  8.  
  9.         t.assign(sz * 2, 0);
  10.     }
  11.  
  12.     void put(int pos, int val) {
  13.         int v = sz + pos;
  14.         t[v] = max(t[v], val);
  15.         v >>= 1;
  16.         while (v) {
  17.             t[v] = max(t[v * 2], t[v * 2 + 1]);
  18.             v >>= 1;
  19.         }
  20.     }
  21.  
  22.     int get_max(int l, int r) {
  23.         l += sz;
  24.         r += sz;
  25.         int res = 0;
  26.         while (l <= r) {
  27.             res = max(res, t[l]);
  28.             res = max(res, t[r]);
  29.             l = (l + 1) >> 1;
  30.             r = (r - 1) >> 1;
  31.         }
  32.         return res;
  33.     }
  34. };
  35.  
  36.  
  37. int n;
  38. vi a;
  39.  
  40. bool read() {
  41.     if  (scanf("%d", &n) < 1) {
  42.         return 0;
  43.     }
  44.     a.resize(n);
  45.     forn(i, n) {
  46.         scanf("%d", &a[i]);
  47.     }
  48.     return 1;
  49. }
  50.  
  51. const int MAXN = 1e5 + 10;
  52.  
  53. int solve() {
  54.     SegmTree dp1(MAXN);
  55.     SegmTree dp2(MAXN);
  56.  
  57.     forn(i, n) {
  58.         int d1 = dp2.get_max(0, a[i] - 1) + 1;
  59.         dp1.put(a[i], d1);
  60.  
  61.         int d2 = dp1.get_max(a[i] + 1, MAXN - 1) + 1;
  62.         dp2.put(a[i], d2);
  63.     }
  64.  
  65.     return max(dp1.get_max(0, MAXN - 1), dp2.get_max(0, MAXN - 1));
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement