fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  7.  
  8. const int inf = 1'000'000'000'000'000'000;
  9.  
  10. struct node {
  11.     int small;
  12.  
  13.     node() {
  14.         small = inf;
  15.     }
  16. };
  17.  
  18. struct segment_tree {
  19.     int size;
  20.     vector<node> tree;
  21.  
  22.     void init(int n) {
  23.         size = 1;
  24.         while (size < n) {
  25.             size <<= 1;
  26.         } tree.assign( size << 1, node() );
  27.     }
  28.  
  29.     node merge_nodes(node& a, node& b) {
  30.         node ret;
  31.         ret.small = min(a.small, b.small);
  32.         return ret;
  33.     }
  34.  
  35.     void build(vector<int>& v, int at, int lx, int rx) {
  36.         if (rx - lx == 1) {
  37.             if ( lx < v.size() ) {
  38.                 tree[at].small = v[lx];
  39.             }
  40.             return;
  41.         }
  42.  
  43.         int mid = lx + (rx - lx) / 2;
  44.         int left = 2 * at + 1;
  45.         int right = 2 * at + 2;
  46.  
  47.         build(v, left, lx, mid);
  48.         build(v, right, mid, rx);
  49.  
  50.         tree[at] = merge_nodes(tree[left], tree[right]);
  51.     }
  52.  
  53.     void build(vector<int>& v) {
  54.         build(v, 0, 0, size);
  55.     }
  56.  
  57.     void update(node& at, int val) {
  58.         at.small = val;
  59.     }
  60.  
  61.     void set(int l, int r, int val, int at, int lx, int rx) {
  62.         if (lx >= r or l >= rx) {
  63.             return;
  64.         }
  65.  
  66.         if (lx >= l and rx <= r) {
  67.             update(tree[at], val);
  68.             return;
  69.         }
  70.  
  71.         int mid = lx + (rx - lx) / 2;
  72.         int left = 2 * at + 1;
  73.         int right = 2 * at + 2;
  74.  
  75.         set(l, r, val, left, lx, mid);
  76.         set(l, r, val, right, mid, rx);
  77.  
  78.         tree[at] = merge_nodes(tree[left], tree[right]);
  79.     }
  80.  
  81.     void set(int l, int r, int val) {
  82.         set(l, r, val, 0, 0, size);
  83.     }
  84.  
  85.     node get(int l, int r, int at, int lx, int rx) {
  86.         if (lx >= r or l >= rx) {
  87.             return node();
  88.         }
  89.  
  90.         if (lx >= l and rx <= r) {
  91.             return tree[at];
  92.         }
  93.  
  94.         int mid = lx + (rx - lx) / 2;
  95.         int left = 2 * at + 1;
  96.         int right = 2 * at + 2;
  97.  
  98.         node left_node = get(l, r, left, lx, mid);
  99.         node right_node = get(l, r, right, mid, rx);
  100.  
  101.         return merge_nodes(left_node, right_node);
  102.     }
  103.  
  104.     node get(int l, int r) {
  105.         return get(l, r, 0, 0, size);
  106.     }
  107.  
  108.     int next_smaller(int l, int r, int val, int at, int lx, int rx) {
  109.         if (lx >= r or l >= rx) {
  110.             return -1;
  111.         }
  112.         if (tree[at].small >= val) {
  113.             return -1;
  114.         }
  115.         if (rx - lx == 1) {
  116.             return lx;
  117.         }
  118.  
  119.         int m = lx + (rx - lx) / 2;
  120.         int left = 2 * at + 1, right = 2 * at + 2;
  121.  
  122.         int ans = next_smaller(l, r, val, left, lx, m);
  123.  
  124.         if (ans == -1) {
  125.             return next_smaller(l, r, val, right, m, rx);
  126.         }
  127.  
  128.         return ans;
  129.     }
  130.  
  131.     int next_smaller(int l, int r, int val) {
  132.         return next_smaller(l, r, val, 0, 0, size);
  133.     }
  134. };
  135.  
  136. void get_shit_done() {
  137.     int n;
  138.     cin >> n;
  139.  
  140.     vector<int> a(n), t(3 * n);
  141.     for (int i = 0; i < n; ++i) {
  142.         cin >> a[i];
  143.         t[i] = a[i];
  144.         t[i + n] = a[i];
  145.         t[i + 2 * n] = a[i];
  146.     }
  147.  
  148.     segment_tree tree;
  149.     tree.init(3 * n);
  150.     tree.build(t);
  151.  
  152.     vector<int> r(3 * n);
  153.     for (int i = 0; i < 3 * n; ++i) {
  154.         int p = tree.next_smaller( i + 1, 3 * n, (t[i] + 1) / 2 );
  155.         if (p == -1) {
  156.             r[i] = 3 * n;
  157.         } else {
  158.             r[i] = p;
  159.         }
  160.     }
  161.  
  162.     segment_tree solve;
  163.     solve.init(3 * n);
  164.     solve.build(r);
  165.  
  166.     for (int i = 0; i < n; ++i) {
  167.         int ans = solve.get(i, i + 2 * n).small;
  168.         if (ans >= i + 2 * n) {
  169.             cout << -1 << ' ';
  170.         } else {
  171.             cout << ans - i << ' ';
  172.         }
  173.     }
  174. }
  175.  
  176. signed main() {
  177.     _3bkarm
  178.  
  179.     int ts = 1;
  180. //    cin >> ts;
  181.     while (ts--) {
  182.         get_shit_done();
  183.     }
  184.  
  185.     return 0;
  186. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/71lsUf
language:
C++ (gcc 8.3)
created:
7 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!