fork(3) download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #include <bits/stdc++.h>
  3. template<int n, typename T>
  4. int lowerBound(const T* __restrict arr, const T val) {
  5. 	if (n == 1) { return val > arr[0]; } 
  6. 	else {
  7. 		constexpr int mid = n / 2;
  8. 		if (val > arr[mid]) { return mid+lowerBound<n-mid, T>(arr+mid, val); }
  9. 		else { return lowerBound<mid, T>(arr,val); }
  10. 	}
  11. };
  12.  
  13. template<int n, typename T>
  14. int loserBound(const T* __restrict arr, const T val) {
  15.     return int(std::lower_bound(arr,arr+n,val)-arr);
  16. }
  17.  
  18. int main() {
  19. 	static int arr[1 << 20];
  20. 	for (int i = 0; i < (1 << 20); i++) { arr[i] = i; }
  21. 	std::mt19937 gen;
  22. 	std::uniform_int_distribution<int> dist(0, 1 << 20);
  23. 	std::vector<int> queries(1 << 23);
  24. 	for (auto &it : queries) { it = dist(gen); }
  25. 	#define TEST(s, f) \
  26. 	{ \
  27. 		std::cout << s << std::endl; \
  28. 		int res = 0; \
  29. 		double tin = (double)clock(), tout; \
  30. 		/* for (int i = 0; i < (1 << 15); i++) { */\
  31. 			for (int q : queries) { \
  32. 				res += f<1<<20>(&arr[0],q); \
  33. 			} \
  34. 		/* } */ \
  35. 		tout = (double)clock(); \
  36. 		std::cout << "time = " << (tout - tin) / CLOCKS_PER_SEC << "s, sum = " << res << std::endl; \
  37. 	}
  38. 	TEST("Testing std::lower_bound...", loserBound);
  39. 	TEST("Testing lowerBound...", lowerBound);
  40. 	return 0;
  41. }
Success #stdin #stdout 2.96s 40036KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Testing std::lower_bound...
time = 1.55678s, sum = 183898710
Testing lowerBound...
time = 1.19021s, sum = 183898710
https://ideone.com/GRd2yj
language:
C++14 (gcc 8.3)
created:
4 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!