fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. static uint64_t x = 1234;
  7. static uint64_t gen() {
  8.     uint64_t z = (x += 0x9e3779b97f4a7c15);
  9.     z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
  10.     z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
  11.     return z ^ (z >> 31);
  12. }
  13.  
  14. template<int n>
  15. struct Segtree {
  16.     vector<int> seg;
  17.     Segtree() : seg(2 * n) {}
  18.     void upd(int j, int x, int i = 1, int l = 0, int r = n) {
  19.         if (r - l == 1) { seg[i] = x; return; }
  20.         int m = (l + r) / 2;
  21.         if (j < m) upd(j, x, 2 * i, l, m);
  22.         else upd(j, x, 2 * i + 1, m, r);
  23.         seg[i] = min(seg[2 * i], seg[2 * i + 1]);
  24.     }
  25.     int query(int lo, int hi, int i = 1, int l = 0, int r = n) {
  26.         if (lo >= r || hi <= l) return INT_MAX;
  27.         if (lo <= l && r <= hi) return seg[i];
  28.         int m = (l + r) / 2;
  29.         return min(query(lo, hi, 2 * i, l, m),
  30.             query(lo, hi, 2 * i + 1, m, r));
  31.     }
  32. };
  33.  
  34. int main() {
  35.     cin.tie(0)->sync_with_stdio(0);
  36.  
  37.     const int n = 1 << 20, q = 1 << 20;
  38.     Segtree<n> seg;
  39.     ll res = 0;
  40.     for (int _ = q; _--;) {
  41.         int i = gen() % n, x = gen() % ((int) 1e9);
  42.         seg.upd(i, x);
  43.         int l = gen() % (n + 1), r = gen() % (n + 1);
  44.         if (l > r) swap(l, r);
  45.         res += seg.query(l, r);
  46.     }
  47.     cout << res << '\n';
  48. }
Success #stdin #stdout 0.76s 11404KB
comments (?)
stdin 
Standard input is empty
stdout 
3713892944
https://ideone.com/vSQNQf
language:
C++14 (gcc 8.3)
created:
2 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!