fork download 
  1. // Fenwick Tree
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cmath>
  5. #include<climits>
  6. #include<cstring>
  7. #include<map>
  8. #define fr(i, zz, zzz) for (int i = zz; i <= zzz; i++)
  9. #define ll long long
  10. #define pii pair<int, int>
  11. #define all(a) a.begin(), a.end()
  12. #define frr(i, zz, zzz) for (int i = zz; i >= zzz; i--)
  13. #define full(asdf) memset(asdf, 0, sizeof(asdf))
  14. #define st first
  15. #define nd second
  16. #define IOS ios_base::sync_with_stdio(0);   cin.tie(0); cout.tie(0);
  17. using namespace std;
  18. const int N = 3E4 + 1;
  19. ll a[N];
  20. int BIT[N];
  21. int n;
  22. int cnt = 1;
  23. int ans = 0;
  24. void digitization() {
  25. 	int cnt = 0;
  26. 	pair<ll, int> tmp[N];
  27. 	cin >> n;
  28. 	fr(i, 1, n) {
  29. 		cin >> a[i];
  30. 		tmp[i].st = a[i];
  31. 		tmp[i].nd = i;
  32. 	}
  33. 	sort(tmp + 1, tmp + n + 1);
  34. 	fr(i, 1, n) {
  35. 		if (tmp[i].st != tmp[i-1].st)
  36. 			++cnt;
  37. 		a[tmp[i].nd] = cnt;
  38. 	}
  39.  
  40. }
  41. ll Get(int pos) {
  42. 	int res = 0;
  43. 	while (pos > 0) {
  44. 		res = max(res, BIT[pos]);
  45. 		pos -= pos & -pos;
  46. 	}
  47.  
  48. 	return res;
  49. }
  50. void Update(int val) {
  51. 	int x = Get(val - 1);
  52. 	ans = max(x, ans);
  53. 	while (val <= n) {
  54. 		BIT[val] = max(BIT[val], x + 1);
  55. 		val += val & -val;
  56. 	}
  57. }
  58. void solve() {
  59. 	fr(i, 1, n) {
  60. 		Update(a[i]);
  61. 	}
  62.  
  63. 	fr(i, 1, n)
  64. 		cout << BIT[i] << " ";
  65. //	cout << Get(n);
  66. }
  67. int main () {
  68. 	IOS
  69. 	digitization();
  70. 	solve();
  71. }
  72.  
  73.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/PdNJPW
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!