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