SHARE
TWEET

Untitled

a guest Oct 16th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int M = 1e2 + 10;
  6. int n, arr[M], seg[4 * M], big = 2e9, g[M], memo[M];
  7. map<int, vector<int>> mp;
  8.  
  9. int build(int l, int r, int i) {
  10.     if (l == r)
  11.         seg[i] = arr[l];
  12.     else
  13.         seg[i] = min(build(l, (l + r) / 2, i * 2 + 1), build((l + r) / 2 + 1, r, i * 2 + 2));
  14.     return seg[i];
  15. }
  16.  
  17. int Min(int l, int r, int L, int R, int i) {
  18.     if (L >= l && R <= r)
  19.         return seg[i];
  20.     if (L > r || R < l)
  21.         return big;
  22.  
  23.     int mid = (L + R) / 2;
  24.     return min(Min(l, r, L, mid, i * 2 + 1), Min(l, r, mid + 1, R, i * 2 + 2));
  25. }
  26.  
  27. int q(int l, int r, int L, int R, int i) {
  28.     if (L >= l && R <= r)
  29.         return seg[i];
  30.     if (L > r || R < l)
  31.         return -1;
  32.     return max(q(l, r, L, (L + R) / 2, i * 2 + 1), q(l, r, (L + R) / 2 + 1, R, i * 2 + 2));
  33. }
  34.  
  35. int firstGreater(int l, int r, int x) {
  36.     if (l == r)
  37.         return (arr[l] > x ? l : -1);
  38.  
  39.     int mid = (l + r) / 2;
  40.  
  41.     if (q(l, mid, 0, n - 1, 0) > x)
  42.         return firstGreater(l, mid, x);
  43.     return firstGreater(mid + 1, r, x);
  44. }
  45.  
  46. int solve(int i) {
  47.     int &r = memo[i];
  48.  
  49.     if (r == -1) {
  50.         if (g[i] == -1) {
  51.             int j = firstGreater(0, n - 1, arr[i]);
  52.             int k = -1;
  53.             int mn = Min(i, n - 1, 0, n - 1, 0);
  54.  
  55.             if (1ll * mn * 2 < arr[i])
  56.                 k = mp[mn][lower_bound(mp[mn].begin(), mp[mn].end(), i) - mp[mn].begin()];
  57.  
  58.             if (k == -1) {
  59.                 mn = Min(0, j, 0, n - 1, 0);
  60.  
  61.                 if (1ll * mn * 2 < arr[i])
  62.                     k = mp[mn][lower_bound(mp[mn].begin(), mp[mn].end(), 0) - mp[mn].begin()];
  63.             }
  64.  
  65.             if (k != -1)
  66.                 if (k > i)
  67.                     r = k - i - 1;
  68.                 else
  69.                     r = n - i + k;
  70.             else
  71.                 r = n - i + solve(j);
  72.  
  73.         } else {
  74.             int k = -1;
  75.             int mn = Min(i, g[i], 0, n - 1, 0);
  76.  
  77.             if (mn * 2 < arr[i])
  78.                 k = mp[mn][lower_bound(mp[mn].begin(), mp[mn].end(), i) - mp[mn].begin()];
  79.  
  80.             if (k != -1)
  81.                 r = k - i;
  82.             else
  83.                 r = g[i] - i + solve(g[i]);
  84.         }
  85.     }
  86.  
  87.     return r;
  88. }
  89.  
  90. int main() {
  91.     ios_base::sync_with_stdio(0);
  92.     cin.tie(0);
  93.  
  94.     cin >> n;
  95.     stack<pair<int, int>> s;
  96.     memset(g, -1, sizeof g);
  97.     memset(memo, -1, sizeof memo);
  98.  
  99.     for (int i = 0; i < n; i++) {
  100.         cin >> arr[i];
  101.  
  102.         mp[arr[i]].push_back(i);
  103.  
  104.         while (!s.empty() && s.top().first < arr[i])
  105.             g[s.top().second] = i, s.pop();
  106.         s.push({arr[i], i});
  107.     }
  108.  
  109.     // return 0;
  110.  
  111.     build(0, n - 1, 0);
  112.  
  113.     for (int i = 0; i < n; i++)
  114.         cout << solve(i) << '\n';
  115.  
  116.     return 0;
  117. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top