fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl     '\n'
  5. #define int      long long
  6.  
  7. const int N = 2e5, oo = 2e18, MOD = 1e9+7;
  8.  
  9. #define mid ((lx + rx) / 2)
  10. #define left_child (2 * nx + 1)
  11. #define right_child (2 * nx + 2)
  12.  
  13. class SegTreeLazy {
  14. public:
  15.     struct Node {
  16.         int sum, lazy, isLazy;
  17.         Node() : sum(0), lazy(0), isLazy(0) { }
  18.         Node(int val) : sum(val), lazy(0), isLazy(0) { } 
  19.         void update(int val, int lx, int rx) {
  20.             sum = (rx - lx) * val;
  21.             lazy = val;
  22.             isLazy = 1;
  23.         }
  24.     };
  25.     Node merge(Node& a, Node& b) {
  26.         Node ret;
  27.         ret.sum = a.sum + b.sum;
  28.         return ret;
  29.     }   
  30.     int tree_size;
  31.     vector<Node> tree;
  32.     SegTreeLazy(int n) {
  33.         tree_size = 1;
  34.         while (tree_size < n) tree_size *= 2;
  35.         tree.assign(2 * tree_size, Node());
  36.     }
  37.     void build(vector<int>& a, int n, int nx, int lx, int rx) {
  38.         if (rx - lx == 1) {
  39.             if (lx < n)
  40.                 tree[nx] = Node(a[lx]);
  41.             return;
  42.         }
  43.  
  44.         build(a, n, left_child, lx, mid);
  45.         build(a, n, right_child, mid, rx);
  46.         tree[nx] = merge(tree[left_child], tree[right_child]);
  47.     }
  48.     void build(vector<int>& arr) {
  49.         build(arr, arr.size(), 0, 0, tree_size);
  50.     }
  51.     void propagate(int nx, int lx, int rx) {
  52.         if (rx - lx == 1 || !tree[nx].isLazy) return;
  53.         tree[left_child].update(tree[nx].lazy, lx, mid);
  54.         tree[right_child].update(tree[nx].lazy, mid, rx);
  55.         tree[nx].lazy = tree[nx].isLazy = 0;
  56.     }
  57.     Node query(int l, int r, int nx, int lx, int rx) {
  58.         if (l >= rx || lx >= r) return Node();
  59.         if (lx >= l && rx <= r) return tree[nx];
  60.  
  61.         propagate(nx, lx, rx);
  62.  
  63.         Node L = query(l, r, left_child, lx, mid);
  64.         Node R = query(l, r, right_child, mid, rx);
  65.         return merge(L, R);
  66.     }
  67.     int query(int l, int r) {
  68.         Node a = query(l, r, 0, 0, tree_size);
  69.         return a.sum;
  70.     }
  71.     void update(int l, int r, int val, int nx, int lx, int rx) {
  72.         propagate(nx, lx, rx);
  73.         if (l >= rx || lx >= r) return;
  74.         if (lx >= l && rx <= r) {
  75.             tree[nx].update(val, lx, rx);
  76.             return;
  77.         }
  78.         update(l, r, val, left_child, lx, mid);
  79.         update(l, r, val, right_child, mid, rx);
  80.  
  81.         tree[nx] = merge(tree[left_child], tree[right_child]);
  82.     }
  83.     void update(int l, int r, int val) {
  84.         update(l, r, val, 0, 0, tree_size);
  85.     }
  86.  
  87. };
  88.  
  89. #undef mid 
  90. #undef left_child 
  91. #undef right_child 
  92.  
  93. void solve() {
  94.     int n; cin >> n;
  95.     vector<int> a(n);
  96.     for (int i = 0; i < n; i++) {
  97.         cin >> a[i];
  98.     }
  99.  
  100.     vector<int> next_greater(n, n);
  101.     stack<int> st;
  102.     for (int i = n-1; i >= 0; i--) {
  103.         while (!st.empty() && a[st.top()] <= a[i]) {
  104.             st.pop();
  105.         }
  106.         if (!st.empty()) 
  107.             next_greater[i] = st.top();
  108.         st.push(i);
  109.     }
  110.  
  111.     SegTreeLazy vis(n);
  112.     int ans = 0;
  113.     stack<int> st2;
  114.     for (int i = 0; i < n-1; i++) {
  115.         if (vis.query(i, i + 1)) {
  116.             st2.push(i);
  117.             continue;
  118.         }
  119.         while (!st2.empty() && (vis.query(st2.top(), st2.top() + 1) || a[st2.top()] <= a[i])) {
  120.             st2.pop();
  121.         }
  122.         if (i == 0 || a[i] <= a[i-1] || a[i] <= a[i + 1]) {
  123.             st2.push(i);
  124.             continue;
  125.         }
  126.         int prev_greater = -1;
  127.         if (!st2.empty())
  128.             prev_greater = st2.top();
  129.  
  130.         st2.push(i);
  131.         int gap = vis.query(prev_greater + 1, i);
  132.         int cnt1 = i - prev_greater - 1 - gap, cnt2 = next_greater[i] - i - 1;
  133.         if (cnt2 < cnt1) {
  134.             vis.update(i + 1, next_greater[i], 1);
  135.             ans += cnt2;
  136.         } else {
  137.             vis.update(prev_greater + 1, i, 1);
  138.             ans += cnt1;
  139.         }
  140.     }
  141.     cout << ans << endl;
  142. }
  143.  
  144.  
  145. signed main() {
  146.     ios_base::sync_with_stdio(false); 
  147.     cin.tie(NULL); cout.tie(NULL);
  148.     // #ifndef ONLINE_JUDGE 
  149.     //    freopen("input.txt", "r", stdin); 
  150.     //    freopen("output.txt", "w", stdout); 
  151.     // #endif 
  152.     int t; t = 1;
  153.     cin >> t;
  154.     while (t--) solve();
  155.     return 0;
  156. }
  157.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/pIR4hs
language:
C++ (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!