fork download
copy 
  1. /**
  2.  *    author:  orzvanh14 (  )
  3.  *    created: 23.12.2022 10:08:02
  4.  *    too lazy to update time
  5. **/
  6. // i wants to take ioi
  7. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13. #define nn "\n"
  14. #define pi pair<int, int>
  15. #define fi first
  16. #define se second
  17. #define lb lower_bound
  18. #define ub upper_bound
  19. #define eb emplace_back
  20. #define pb push_back
  21. #define TASK " "
  22.  
  23. #define ms(a, x) memset(a, x, sizeof(a))
  24. #define all(a) a.begin(), a.end()
  25. #define All(a, n) a + 1, a + 1 + n
  26.  
  27. #define LOG 19
  28.  
  29. const int INF = 1e18;
  30. const int mod = 1e9 + 7;
  31. const int N = 2e5 + 5;
  32.  
  33. int n;
  34. int a[N];
  35.  
  36. struct node{
  37. 	int len, cnt;
  38. };
  39.  
  40. node st[4 * N];
  41.  
  42. vector<int> v;
  43.  
  44. void nhap(){
  45. 	cin >> n;
  46. 	for(int i = 1; i <= n; i++){
  47. 		cin >> a[i];
  48. 		v.pb(a[i]);
  49. 	}
  50. }
  51.  
  52. node merge(node a, node b){
  53. 	if(a.len > b.len) return a;
  54. 	if(a.len < b.len) return b;
  55.  
  56. 	if(a.len == 0) return {0, 0};
  57.  
  58. 	return {a.len, (a.cnt + b.cnt) % mod};
  59. }
  60.  
  61. void update(int id, int l, int r, int i, node val){
  62. 	if(l > i || r < i) return;
  63.  
  64. 	if(l == r){
  65. 		if(val.len > st[id].len){
  66. 			st[id] = val;
  67. 		}
  68. 		else if(val.len == st[id].len){
  69. 			st[id].cnt += val.cnt;
  70. 			st[id].cnt %= mod;
  71. 		}
  72. 		return;
  73. 	}
  74.  
  75. 	int m = (l + r) / 2;
  76.  
  77. 	update(id * 2, l, m, i, val);
  78. 	update(id * 2 + 1, m + 1, r, i, val);
  79.  
  80. 	st[id] = merge(st[id * 2], st[id * 2 + 1]);
  81. }
  82.  
  83. node get(int id, int l, int r, int u, int v){
  84. 	if(l > v || r < u) return {0, 0};
  85.  
  86. 	if(l >= u && r <= v){
  87. 		return st[id];
  88. 	}
  89.  
  90. 	int m = (l + r) / 2;
  91.  
  92. 	return merge(
  93. 		get(id * 2, l, m, u, v),
  94. 		get(id * 2 + 1, m + 1, r, u, v)
  95. 	);
  96. }
  97.  
  98. void solve(){
  99.  
  100. 	sort(all(v));
  101.  
  102. 	for(int i = 1; i <= n; i++){
  103.  
  104. 		int pos = lb(all(v), a[i]) - v.begin() + 1;
  105.  
  106. 		node best;
  107.  
  108. 		if(pos == 1){
  109. 			best = {0, 0};
  110. 		}
  111. 		else{
  112. 			best = get(1, 1, n, 1, pos - 1);
  113. 		}
  114.  
  115. 		node cur;
  116.  
  117. 		cur.len = best.len + 1;
  118.  
  119. 		if(best.len == 0){
  120. 			cur.cnt = 1;
  121. 		}
  122. 		else{
  123. 			cur.cnt = best.cnt;
  124. 		}
  125.  
  126. 		update(1, 1, n, pos, cur);
  127. 	}
  128.  
  129. 	cout << st[1].cnt % mod;
  130. }
  131.  
  132. signed main() {
  133. 	// freopen("piggyback.in", "r", stdin);
  134. 	// freopen("piggyback.out", "w", stdout);
  135. 	ios_base::sync_with_stdio(0);
  136. 	cin.tie(0);
  137. 	cout.tie(0);
  138.  
  139. 	nhap();
  140. 	solve();
  141.  
  142. 	return 0;
  143. }
Success #stdin #stdout 0s 5532KB
comments (?)
stdin
copy 
7
1 1 2 2 4 3 3
stdout
copy 
12
https://ideone.com/3eE85M
language:
C++14 (gcc 8.3)
created:
2 days 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!