fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. constexpr int MAXN = (1 << 20);
  5. constexpr int MAXLOG = 20;
  6.  
  7. struct SparseTable
  8. {
  9. 	int sparse[MAXN][MAXLOG];
  10. 	int prec_lg2[MAXN];
  11. 	int n;
  12.  
  13. 	SparseTable(const vector<int> &a)
  14. 		: n { 0 }
  15. 	{ 
  16. 		memset(sparse, 0, sizeof(sparse)); 
  17. 		memset(prec_lg2, 0, sizeof(prec_lg2));
  18. 		init(a);
  19. 	}
  20.  
  21. 	int operation(const int a , const int b){
  22. 		return min(a , b);
  23. 	}
  24.  
  25. 	void init(const vector<int> &a) 
  26. 	{
  27. 		n = a.size();
  28.  
  29. 		for(int i = 2 ; i < 2 * n ; ++i)
  30. 		{
  31. 			prec_lg2[i] = prec_lg2[i >> 1] + 1;
  32. 		}
  33.  
  34. 		for(int i = 0 ; i < n ; ++i)
  35. 		{
  36. 			sparse[i][0] = a[i];
  37. 		}
  38.  
  39. 		for(int j = 1 ; (1 << j) <= n ; ++j)
  40. 		{    
  41. 			for(int i = 0; i < n ; ++i)
  42. 			{
  43. 				sparse[i][j] = operation(sparse[i][j - 1], sparse[i + (1 << (j - 1))][j - 1]);
  44. 			}
  45. 		}
  46. 	}
  47.  
  48. 	int query(int l, int r) //[l,r]
  49. 	{ 
  50. 		int k = prec_lg2[r - l + 1];
  51. 		return operation(sparse[l][k], sparse[r - (1 << k) + 1][k]);
  52. 	}
  53. };
  54.  
  55. int main() {
  56. 	int n;
  57. 	while(cin >> n)
  58. 	{
  59. 		assert(n > 1);
  60.  
  61. 		vector<int> v(n);
  62. 		for(auto& el : v)
  63. 			cin >> el;
  64.  
  65. 		SparseTable sparse_table(v);
  66.  
  67. 		cout << "0 0 ";
  68.  
  69. 		auto bin_search = [&sparse_table,&v](int r_ind , int cur_value)
  70. 		{
  71. 			int l = 0 , r = r_ind - 1;
  72. 			if(v[r] < cur_value)
  73. 				return r;
  74. 			if(sparse_table.query(0 , r_ind - 1) >= cur_value)
  75. 				return -1;
  76.  
  77. 			while(r - l > 1)
  78. 			{
  79. 				int mid = (r + l) / 2;
  80. 				if(sparse_table.query(mid , r_ind - 1) < cur_value)
  81. 				{
  82. 					l = mid;
  83. 				}
  84. 				else
  85. 				{
  86. 					r = mid;
  87. 				}
  88. 			}
  89.  
  90. 			return l;
  91. 		};
  92.  
  93. 		for(int cur = 2 ; cur < n ; ++cur)
  94. 		{
  95. 			int i = bin_search(cur , v[cur]);
  96. 			if(i == -1)
  97. 			{
  98. 				cout << 0 << " ";
  99. 				continue;
  100. 			}
  101.  
  102. 			int j = bin_search(i , v[cur]);
  103. 			cout << (j == -1 ? 0 : v[j]) << " ";
  104. 		}
  105.  
  106. 		cout << endl;
  107. 	}
  108.  
  109. 	return 0;
  110. }
Success #stdin #stdout 0.04s 101120KB
comments (?)
stdin
copy 
8
2 4 5 3 1 7 10 8

10
1 2 3 4 2 3 7 8 2 1

8
1 2 3 4 5 6 7 8

8
8 7 6 5 4 3 2 1

3
7 5 10

3
7 5 6

8
2 2 2 2 2 2 2 2
stdout
copy 
0 0 2 0 0 3 1 1 
0 0 1 2 0 2 2 3 0 0 
0 0 1 2 3 4 5 6 
0 0 0 0 0 0 0 0 
0 0 7 
0 0 0 
0 0 0 0 0 0 0 0
https://ideone.com/7DSClT
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!