fork(5) download
  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 double arr[1 << 20];
  20. for (int i = 0; i < (1 << 20); i++) { arr[i] = i; }
  21. std::mt19937 gen;
  22. std::uniform_real_distribution<double> dist(0, 1 << 20);
  23. std::vector<double> queries(1 << 9);
  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 (auto 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 3.92s 11876KB
stdin
Standard input is empty
stdout
Testing std::lower_bound...
time = 3.0665s, sum = 588382208
Testing lowerBound...
time = 0.853522s, sum = 588382208