fork download 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 2e5 + 5; 
  11.  
  12. int n; 
  13. int a[N]; 
  14. int f[18][N]; // f[k][i] = min của đoạn bắt đầu từ i và có độ dài 2^k
  15.  
  16. void precompute() { // O(n * log2(n))
  17. 	for (int i = 1; i <= n; i++) f[0][i] = a[i];  
  18.  
  19. 	for (int k = 1; (1 << k) <= n; k++) {
  20. 		for (int i = 1; i + (1 << k) - 1 <= n; i++) {
  21. 			f[k][i] = min(f[k - 1][i], f[k - 1][i + (1 << (k - 1))]); 
  22. 		}
  23. 	}
  24. }
  25.  
  26. // min của đoạn [l, r]
  27. int getMin(int l, int r) { // O(1)
  28. 	int k = log2(r - l + 1); 
  29. 	return min(f[k][l], f[k][r - (1 << k) + 1]); 
  30. }
  31.  
  32. // tìm phần tử gần nhất bên trái < a[i]
  33. int getLeftSmaller(int i) { // O(log2(n))
  34. 	int l = 1, r = i - 1, ans = 0;  
  35. 	while (l <= r) {
  36. 		int mid = (l + r) >> 1; 
  37.  
  38. 		if (getMin(mid, i) < a[i]) {
  39. 			ans = mid; 
  40. 			l = mid + 1; 
  41. 		}
  42. 		else {
  43. 			r = mid - 1; 
  44. 		}
  45. 	}
  46. 	return ans; 
  47. }
  48.  
  49. int main() {
  50. 	ios::sync_with_stdio(0); cin.tie(0);  	
  51. 	cin >> n;
  52. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  53.  
  54. 	precompute();  
  55.  
  56. 	for (int i = 1; i <= n; i++) {
  57. 		cout << getLeftSmaller(i) << ' '; 
  58. 	}
  59. }
Success #stdin #stdout 0.01s 5776KB
comments (?)
stdin 
8
2 5 1 4 8 3 2 5
stdout 
0 1 0 3 4 3 3 7
https://ideone.com/yQXbjn
language:
C++14 (gcc 8.3)
created:
1 year 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!