fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define F first
  6. #define S second
  7. #define pb push_back
  8. #define pii pair<int,int>
  9.  
  10. const int N = 2e5 + 5;
  11.  
  12. struct BIT {
  13.     int n;
  14.     vector<int> bit;
  15.  
  16.     BIT() {}
  17.     BIT(int n) : n(n) {
  18.         bit.assign(n + 3, 0);
  19.     }
  20.  
  21.     void update(int id, int val) {
  22.         for (int i = id; i <= n; i += (i & -i)) {
  23.             bit[i] = max(bit[i], val);
  24.         }
  25.     }
  26.  
  27.     int get(int id) {
  28.         int ret = 0;
  29.         for (int i = id; i > 0; i -= (i & -i)) {
  30.             ret = max(ret, bit[i]);
  31.         }
  32.         return ret;
  33.     }
  34. } lis;
  35.  
  36. struct BIT2 {
  37.     int n;
  38.     vector<int> bit;
  39.  
  40.     BIT2() {}
  41.     BIT2(int n) : n(n) {
  42.         bit.assign(n + 3, 0);
  43.     }
  44.  
  45.     void update(int id, int val) {
  46.         for (int i = id; i <= n; i += (i & -i)) {
  47.             bit[i] = max(bit[i], val);
  48.         }
  49.     }
  50.  
  51.     int get(int id) {
  52.         id = max(1, id);
  53.         int ret = 0;
  54.         for (int i = id; i <= n; i += (i & -i)) {
  55.             ret = max(ret, bit[i]);
  56.         }
  57.         return ret;
  58.     }
  59. } lds;
  60.  
  61. int n, a[N], pre[N], suf[N], f[N], cost[N];
  62.  
  63. void solve() {
  64.     cin >> n;
  65.     for (int i = 1; i <= n; i++) {
  66.         cin >> a[i];
  67.     }
  68.     set<int> s;
  69.     s.insert(0);
  70.     s.insert(n + 1);
  71.     f[0] = f[n + 1] = 0;
  72.     for (int i = 1; i <= n; i++) {
  73.         auto it = --s.upper_bound(a[i]);
  74.         pre[i] = *it;
  75.         suf[i] = *(++it);
  76.         s.insert(a[i]);
  77.         f[pre[i]]++;
  78.         f[a[i]] = f[pre[i]];
  79.         cost[i] = f[a[i]];
  80.     }
  81.     int res = 0;
  82.     lis = BIT(n);
  83.     lds = BIT2(n);
  84.     for (int i = n; i >= 1; i--) {
  85.         res = max(res, cost[i] + lis.get(pre[i]) + lds.get(pre[i]));
  86.         res = max(res, cost[i] + lis.get(suf[i]) + lds.get(suf[i]));
  87.         lis.update(a[i], lis.get(a[i]) + 1);
  88.         lds.update(a[i], lds.get(a[i]) + 1);
  89.     }
  90.     cout << res << '\n';
  91. }
  92.  
  93. signed main() {
  94.     ios_base::sync_with_stdio(0);
  95.     cin.tie(0);
  96.     int T;
  97.     cin >> T;
  98.     while (T--) {
  99.         solve();
  100.     }
  101. }
Success #stdin #stdout 0.01s 5728KB
comments (?)
stdin
copy 
1
5
1 4 5 2 3
stdout
copy 
6
https://ideone.com/6fLUWc
language:
C++14 (gcc 8.3)
created:
9 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!