fork download
copy 
  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. const int MOD = 1e9 + 7;
  12.  
  13. void add(int& a, int b) {
  14. 	a += b; 
  15. 	if (a >= MOD) a -= MOD;  
  16. }
  17.  
  18. int n;  
  19. int a[N]; 
  20.  
  21. void compress(int a[]) {
  22. 	vector<int> vals;  
  23. 	for (int i = 1; i <= n; i++) vals.push_back(a[i]);  
  24.  
  25. 	sort(vals.begin(), vals.end());  
  26. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());   
  27.  
  28. 	for (int i = 1; i <= n; i++) {
  29. 		a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();  
  30. 	}
  31. }
  32.  
  33. struct fenwick {
  34. 	int n; 
  35. 	vector<int> ft; 
  36.  
  37. 	fenwick(int n): n(n) {
  38. 		ft.resize(n); 
  39. 	}
  40.  
  41. 	void update(int pos, int val) {
  42. 		for (; pos < n; pos = pos | (pos + 1)) add(ft[pos], val); 
  43. 	}
  44.  
  45. 	int get(int pos) {
  46. 		int ans = 0;  
  47. 		for (; pos >= 0; pos = (pos & (pos + 1)) - 1) add(ans, ft[pos]); 
  48. 		return ans; 
  49. 	}
  50. }; 
  51.  
  52. int dp[N]; // dp[i] = số dãy con tăng kết thúc tại i 
  53.  
  54. int main() {
  55. 	ios::sync_with_stdio(0); cin.tie(0);  	
  56. 	cin >> n; 
  57. 	for (int i = 1; i <= n; i++) cin >> a[i];  
  58.  
  59. 	compress(a);  
  60.  
  61. 	fenwick BIT(n);   
  62.  
  63. 	for (int i = 1; i <= n; i++) {
  64. 		dp[i] = 1;  
  65. 		add(dp[i], BIT.get(a[i] - 1)); 
  66. 		BIT.update(a[i], dp[i]); 
  67. 	}
  68.  
  69. 	int ans = 0;   
  70. 	for (int i = 1; i <= n; i++) add(ans, dp[i]);  
  71.  
  72. 	cout << ans << '\n'; 
  73. }
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
3
2 1 3
stdout
copy 
5
https://ideone.com/0ufJZ2
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!