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. struct Node {
  15.     int val, l, r;
  16.     Node *lc, *rc;
  17.     Node(int l, int r) : l(l), r(r), val(0) {
  18.         if (r - l > 1) {
  19.             int m = (l + r) / 2;
  20.             lc = new Node(l, m), rc = new Node(m, r);
  21.         }
  22.     }
  23.     void upd(int i, int x)  {
  24.         if (r - l == 1) val = x;
  25.         else (i < (l + r) / 2 ? lc : rc)->upd(i, x);
  26.     }
  27.     int query(int lo, int hi) {
  28.         if (lo >= r || hi <= l) return INT_MAX;
  29.         if (lo <= l && r <= hi) return val;
  30.         int m = (l + r) / 2;
  31.         return min(lc->query(lo, hi), rc->query(lo, hi));
  32.     }
  33. };
  34.  
  35. int main() {
  36.     cin.tie(0)->sync_with_stdio(0);
  37.  
  38.     const int n = 1 << 20, q = 1 << 20;
  39.     Node seg(0, n);
  40.     ll res = 0;
  41.     for (int _ = q; _--;) {
  42.         int i = gen() % n, x = gen() % ((int) 1e9);
  43.         seg.upd(i, x);
  44.         int l = gen() % (n + 1), r = gen() % (n + 1);
  45.         if (l > r) swap(l, r);
  46.         res += seg.query(l, r);
  47.     }
  48.     cout << res << '\n';
  49. }
Success #stdin #stdout 2.53s 101904KB
comments (?)
stdin 
Standard input is empty
stdout 
3713892944
https://ideone.com/bVYKZ3
language:
C++14 (gcc 8.3)
created:
15 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!