fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <random>
  5.  
  6. using namespace std;
  7.  
  8. mt19937 mt(123);
  9.  
  10. const int N = 1 << 17;
  11. int dat[N * 2];
  12.  
  13. void update(int k, int v) {
  14.   dat[k + N] = v;
  15.   for (int i = k + N >> 1; i > 0; i >>= 1) {
  16.     dat[i] = min(dat[i * 2], dat[i * 2 + 1]);
  17.   }
  18. }
  19.  
  20. int query(int l, int r) {
  21.   int res = 1e9;
  22.   l += N;
  23.   r += N;
  24.   while (l < r) {
  25.     if (l & 1) res = min(res, dat[l++]);
  26.     if (r & 1) res = min(res, dat[--r]);
  27.     l >>= 1;
  28.     r >>= 1;
  29.   }
  30.   return res;
  31. }
  32.  
  33. int s;
  34. double r;
  35. void bench_random() {
  36.   clock_t start = clock();
  37.   for (int i = 0; i < 10000000; i++) {
  38.     int a = uniform_int_distribution<int>(0, N - 2)(mt);
  39.     int b = uniform_int_distribution<int>(0, N - 2)(mt);
  40.     s += a;
  41.     s += b;
  42.   }
  43.   clock_t end = clock();
  44.   r = (double)(end - start) / CLOCKS_PER_SEC;
  45.   printf("random: %.4f\n", r);
  46. }
  47.  
  48. void bench_update() {
  49.   clock_t start = clock();
  50.   for (int i = 0; i < 10000000; i++) {
  51.     int k = uniform_int_distribution<int>(0, N - 2)(mt);
  52.     int v = uniform_int_distribution<int>(0, N - 2)(mt);
  53.     update(k, v);
  54.   }
  55.   clock_t end = clock();
  56.   printf("update: %.4f\n", (double)(end - start) / CLOCKS_PER_SEC);
  57.   printf("update-random: %.4f\n", (double)(end - start) / CLOCKS_PER_SEC - r);
  58. }
  59.  
  60. void bench_query() {
  61.   clock_t start = clock();
  62.   for (int i = 0; i < 10000000; i++) {
  63.     int l = uniform_int_distribution<int>(0, N - 2)(mt);
  64.     int r = uniform_int_distribution<int>(0, N - 2)(mt);
  65.     if (l > r) swap(l, r);
  66.     s += query(l, r + 1);
  67.   }
  68.   clock_t end = clock();
  69.   printf("query: %.4f\n", (double)(end - start) / CLOCKS_PER_SEC);
  70.   printf("query-random: %.4f\n", (double)(end - start) / CLOCKS_PER_SEC - r);
  71.   printf("result: %d\n", s);
  72. }
  73.  
  74. int main() {
  75.   for (int i = 0; i < N - 2; i++) {
  76.     update(i, uniform_int_distribution<int>(0, N - 2)(mt));
  77.   }
  78.   bench_random();
  79.   bench_update();
  80.   bench_query();
  81. }
  82.  
  83.  
Success #stdin #stdout 2.54s 16264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
random: 0.4573
update: 0.7776
update-random: 0.3203
query: 1.3026
query-random: 0.8453
result: 864747476
https://ideone.com/Lo1vJQ
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!