fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e6 + 5; 
  12. const int MOD = 1e9 + 7;  
  13.  
  14. int add(int a, int b) {
  15. 	return (a + b) % MOD; 
  16. }
  17.  
  18. int n; 
  19. int a[N];
  20. int k[N]; 
  21.  
  22. void compress(int a[]) {
  23. 	vector<int> vals; 
  24. 	for (int i = 1; i <= n; i++) vals.push_back(a[i]); 
  25. 	sort(vals.begin(), vals.end());   
  26. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin()); 
  27. 	for (int i = 1; i <= n; i++) {
  28. 		a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin(); 
  29. 	}
  30. }
  31.  
  32. int seg[4 * N]; 
  33.  
  34. void update(int id, int l, int r, int pos, int val) {
  35. 	if (l > pos || r < pos) return;  
  36. 	if (l == r) {
  37. 		seg[id] += val;  
  38. 		return; 
  39. 	}
  40. 	int mid = (l + r) >> 1; 
  41. 	update(id * 2, l, mid, pos, val); 
  42. 	update(id * 2 + 1, mid + 1, r, pos, val); 
  43. 	seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  44. }
  45.  
  46. // Tìm i nhỏ nhất sao cho sum[1..i] >= k
  47. int findKth(int id, int l, int r, int k) {
  48. 	if (k > seg[id]) return n + 1;  
  49. 	if (l == r) return l;  
  50. 	int mid = (l + r) >> 1;  
  51. 	int res = findKth(id * 2, l, mid, k); 
  52. 	if (res == n + 1) res = findKth(id * 2 + 1, mid + 1, r, k - seg[id * 2]);  
  53. 	return res; 
  54. }
  55.  
  56. int last[N]; 
  57. int nxt[N]; // nxt[l] = vị trí l' gần nhất > l sao cho a[l'] = a[l]  
  58. int first_r[N]; // first_r[l] = đầu mút r nhỏ nhất thoả mãn đoạn [l, r] có >= k[l] giá trị phân biệt
  59.  
  60. void precompute() {
  61. 	for (int l = n; l >= 1; l--) {
  62. 		nxt[l] = (last[a[l]] == 0) ? n + 1 : last[a[l]];  
  63. 		last[a[l]] = l;  
  64. 	}
  65.  
  66. 	for (int l = n; l >= 1; l--) {
  67. 		if (nxt[l] <= n) update(1, 1, n, nxt[l], -1); 
  68. 		update(1, 1, n, l, 1); 
  69. 		first_r[l] = findKth(1, 1, n, k[l]); 
  70. 	}
  71. }
  72.  
  73. int dp[N]; // dp[l] = có bao nhiêu cách phân rã đoạn [l, n] 
  74. int suf_dp[N]; // suf_dp[l] = tổng các dp[l], dp[l + 1],..., dp[n] 
  75.  
  76. int main() {
  77. 	ios::sync_with_stdio(false); 
  78. 	cin.tie(nullptr);  	
  79. 	cin >> n; 
  80. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  81. 	for (int i = 1; i <= n; i++) cin >> k[i];  
  82.  
  83.  	compress(a);  
  84. 	precompute();
  85.  
  86. 	dp[n + 1] = suf_dp[n + 1] = 1;  
  87. 	for (int l = n; l >= 1; l--) {
  88. 		dp[l] = add(dp[l], suf_dp[first_r[l] + 1]);
  89. 		suf_dp[l] = add(suf_dp[l + 1], dp[l]); 
  90. 	}
  91.  
  92. 	cout << dp[1] << '\n'; 
  93. }
Success #stdin #stdout 0.01s 15912KB
comments (?)
stdin 
4
1 1 2 2
2 1 1 1
stdout 
2
https://ideone.com/icpaJl
language:
C++14 (gcc 8.3)
created:
36 days 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!