fork(5) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <random>
  4. #include <ctime>
  5. using namespace std;
  6.  
  7. const int N = 4e7;
  8. int a[N];
  9. int link[N];
  10. int stack[N];
  11. int ptr = 0;
  12.  
  13. void with_stack() {
  14. 	fill_n(link, N, -1);
  15. 	for (int i = 0; i < N; ++i) {
  16. 		while (ptr > 0 && a[stack[ptr - 1]] <= a[i]) {
  17. 			--ptr;
  18. 		}
  19. 		if (ptr) {
  20. 			link[i] = stack[ptr - 1];
  21. 		}
  22. 		stack[ptr++] = i;
  23. 	}
  24. }
  25.  
  26. void without_stack() {
  27. 	for (int i = 0; i < N; ++i) {
  28. 		int &l = link[i];
  29. 		l = i - 1;
  30. 		while (l >= 0 && a[l] <= a[i]) {
  31. 			l = link[l];
  32. 		}
  33. 	}		
  34. }
  35.  
  36. int main() {
  37. 	mt19937 randint;
  38. 	for (int i = 0; i < N; ++i) {
  39. 		a[i] = (int)randint();
  40. 	}
  41.  
  42. 	long long start = clock();
  43.  
  44. 	//with_stack();
  45. 	//without_stack();
  46.  
  47. 	long long finish = clock();
  48.  
  49. 	cout << 1000 * (finish - start) / CLOCKS_PER_SEC << " ms\n";
  50.  
  51. 	return 0;
  52. }
Success #stdin #stdout 0.52s 483968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
386 ms
https://ideone.com/fkZ1t6
language:
C++14 (gcc 8.3)
created:
5 years 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!