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. struct Segtree {
  15.     int n;
  16.     vector<int> seg;
  17.     Segtree(int _n) {
  18.         for (n = 1; n < _n; n *= 2);
  19.         seg.resize(2 * n);
  20.     }
  21.     void upd(int i, int x) {
  22.         seg[i += n] = x;
  23.         while (i /= 2) seg[i] = min(seg[2 * i], seg[2 * i + 1]);
  24.     }
  25.     int query(int l, int r) {
  26.         int res = INT_MAX;
  27.         for (l += n, r += n; l < r; l /= 2, r /= 2) {
  28.             if (l & 1) res = min(res, seg[l++]);
  29.             if (r & 1) res = min(seg[--r], res);
  30.         }
  31.         return res;
  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.     Segtree seg(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 0.33s 11460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3713892944
https://ideone.com/FOEkvi
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!