fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 2e9;
  5. const int MINF = -2e9;
  6.  
  7. int n;
  8. vector<int> A, P, M, Q, K, BL, BR, tree_seg;
  9.  
  10. void build(int node, int l, int r) {
  11.     if (l == r) {
  12.         tree_seg[node] = BR[l];
  13.         return;
  14.     }
  15.     int mid = l + (r - l) / 2;
  16.     build(2 * node, l, mid);
  17.     build(2 * node + 1, mid + 1, r);
  18.     tree_seg[node] = min(tree_seg[2 * node], tree_seg[2 * node + 1]);
  19. }
  20.  
  21. int query(int node, int l, int r, int ql, int qr, int x) {
  22.     if (l > qr || r < ql || tree_seg[node] >= x) return -1;
  23.     if (l == r) return l;
  24.     int mid = l + (r - l) / 2;
  25.     int res = query(2 * node, l, mid, ql, qr, x);
  26.     if (res != -1) return res;
  27.     return query(2 * node + 1, mid + 1, r, ql, qr, x);
  28. }
  29.  
  30. int getMaxY_Q(int val, int lenR) {
  31.     int low = 0, high = lenR, ans = 0;
  32.     while (low <= high) {
  33.         int mid = low + (high - low) / 2;
  34.         if (Q[mid] > val) { ans = mid; low = mid + 1; } 
  35.         else high = mid - 1;
  36.     }
  37.     return ans;
  38. }
  39.  
  40. int getMaxY_K(int val, int lenR) {
  41.     int low = 0, high = lenR, ans = 0;
  42.     while (low <= high) {
  43.         int mid = low + (high - low) / 2;
  44.         if (K[mid] < val) { ans = mid; low = mid + 1; } 
  45.         else high = mid - 1;
  46.     }
  47.     return ans;
  48. }
  49.  
  50. int getMaxX_P(int val, int lenL) {
  51.     int low = 0, high = lenL, ans = 0;
  52.     while (low <= high) {
  53.         int mid = low + (high - low) / 2;
  54.         if (P[mid] > val) { ans = mid; low = mid + 1; } 
  55.         else high = mid - 1;
  56.     }
  57.     return ans;
  58. }
  59.  
  60. int getMaxX_M(int val, int lenL) {
  61.     int low = 0, high = lenL, ans = 0;
  62.     while (low <= high) {
  63.         int mid = low + (high - low) / 2;
  64.         if (M[mid] < val) { ans = mid; low = mid + 1; } 
  65.         else high = mid - 1;
  66.     }
  67.     return ans;
  68. }
  69.  
  70. void solve() {
  71.     cin >> n;
  72.     A.assign(n + 1, 0);
  73.     for (int i = 1; i <= n; i++) cin >> A[i];
  74.  
  75.     int lenL = 0;
  76.     P.assign(n + 1, 0); M.assign(n + 1, 0);
  77.     P[0] = INF; M[0] = MINF;
  78.     for (int i = 1; i <= n; i++) {
  79.         if (i == 1) { lenL = 1; P[1] = A[1]; M[1] = A[1]; } 
  80.         else {
  81.             if (A[i] < P[i - 1]) { lenL = i; P[i] = A[i]; M[i] = M[i - 1]; } 
  82.             else if (A[i] > M[i - 1]) { lenL = i; P[i] = P[i - 1]; M[i] = A[i]; } 
  83.             else break;
  84.         }
  85.     }
  86.  
  87.     int lenR = 0;
  88.     Q.assign(n + 1, 0); K.assign(n + 1, 0);
  89.     Q[0] = INF; K[0] = MINF;
  90.     for (int j = 1; j <= n; j++) {
  91.         int idx = n - j + 1;
  92.         if (j == 1) { lenR = 1; Q[1] = A[idx]; K[1] = A[idx]; } 
  93.         else {
  94.             if (A[idx] < Q[j - 1]) { lenR = j; Q[j] = A[idx]; K[j] = K[j - 1]; } 
  95.             else if (A[idx] > K[j - 1]) { lenR = j; Q[j] = Q[j - 1]; K[j] = A[idx]; } 
  96.             else break;
  97.         }
  98.     }
  99.  
  100.     BL.assign(lenL + 1, 0);
  101.     for (int x = 1; x <= lenL; x++) {
  102.         if (x == 1) BL[x] = max(getMaxY_Q(A[1], lenR), getMaxY_K(A[1], lenR));
  103.         else {
  104.             if (A[x] < P[x - 1]) BL[x] = getMaxY_Q(A[x], lenR);
  105.             else BL[x] = getMaxY_K(A[x], lenR);
  106.         }
  107.     }
  108.  
  109.     BR.assign(lenR + 1, 0);
  110.     for (int y = 1; y <= lenR; y++) {
  111.         int idx = n - y + 1;
  112.         if (y == 1) BR[y] = max(getMaxX_P(A[n], lenL), getMaxX_M(A[n], lenL));
  113.         else {
  114.             if (A[idx] < Q[y - 1]) BR[y] = getMaxX_P(A[idx], lenL);
  115.             else BR[y] = getMaxX_M(A[idx], lenL);
  116.         }
  117.     }
  118.  
  119.     tree_seg.assign(4 * lenR + 5, 0);
  120.     if (lenR > 0) build(1, 1, lenR);
  121.  
  122.     vector<int> dp(lenL + 1, -1);
  123.     dp[0] = lenR;
  124.     int ans = dp[0];
  125.  
  126.     for (int x = 1; x <= lenL; x++) {
  127.         int y_curr = min({dp[x - 1], BL[x], n - x});
  128.         if (y_curr < 0) {
  129.             dp[x] = -1;
  130.             continue;
  131.         }
  132.         int limit = min(lenR, n - x);
  133.         if (y_curr < limit) {
  134.             int k = query(1, 1, lenR, y_curr + 1, limit, x);
  135.             if (k != -1) y_curr = k - 1;
  136.             else y_curr = limit;
  137.         }
  138.         dp[x] = y_curr;
  139.         ans = max(ans, x + dp[x]);
  140.     }
  141.     cout << ans << "\n";
  142. }
  143.  
  144. int main() {
  145.     ios_base::sync_with_stdio(false);
  146.     cin.tie(NULL);
  147.     int t;
  148.     if (cin >> t) {
  149.         while (t--) solve();
  150.     }
  151.     return 0;
  152. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
3
5
3 1 4 1 5
3
2 2 1
16
3 4 5 7 12 15 1 15 16 8 14 2 16 14 9 2
stdout
copy 
4
2
11
https://ideone.com/O7lxyL
language:
C++14 (gcc 8.3)
created:
7 hours 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!