fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define rep(i, n) for (int i = 0;  i < (n); ++i)
  5.  
  6. const int n = 1 << 22;
  7. int dat[2 * n];
  8.  
  9. void init() {
  10.   for (int i = n - 1; i > 0; --i) dat[i] = min(dat[2*i], dat[2*i+1]);
  11. }
  12.  
  13. void update(int k, int a) {
  14. 	k += n;
  15. 	dat[k] = a;
  16. 	while (k > 1) {
  17. 		k /= 2;
  18. 		dat[k] = min(dat[2*k], dat[2*k+1]);
  19. 	} 
  20. }
  21.  
  22. int query(int a, int b, int k = 1, int l = 0, int r = n) {
  23. 	if (r <= a || b <= l) return INT_MAX;
  24. 	if (a <= l && r <= b) return dat[k];
  25. 	else {
  26. 		int vl = query(a, b, 2*k, l, (l+r)/2);
  27. 		int vr = query(a, b, 2*k+1, (l+r)/2, r);
  28. 		return min(vl, vr);
  29. 	}
  30. }
  31.  
  32. int main() {
  33. 	rep(i, n) dat[i + n] = i;
  34. 	init();
  35. 	bool f = true;
  36. 	rep(i, n) {
  37. 		int l = rand()%n, r = rand()%n;
  38. 		if (l == r) continue;
  39. 		if (l > r) swap(l, r);
  40. 		f &= query(l, r) == l;
  41. 	}
  42. 	cout << (f ? "OK" : "NG") << endl;
  43. }
Success #stdin #stdout 2.9s 36240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
OK
https://ideone.com/u0EodD
language:
C++14 (gcc 8.3)
created:
7 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!