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.  
  30. const int INF = 1e18;
  31. const int mod = 1e9+7;
  32. const int N = 3e4  + 5;
  33. int MOD = 998244353;
  34. int bit[200000];
  35. struct node{
  36. 	int kc, u, hk;
  37. 	bool operator<(const node& other) const {
  38.         return kc > other.kc;
  39.     }
  40. };
  41. struct edge{
  42. 	int v, w, h;
  43. };
  44. int n;
  45. int a[N];
  46. int st[4 * N];
  47.  
  48. vector<int> v;
  49. void nhap(){
  50.     cin >> n;
  51.     for(int i = 1; i <= n; i++){
  52.         cin >> a[i];
  53.         v.pb(a[i]);
  54.     }
  55.     sort(all(v));
  56.     v.erase(unique(all(v)), v.end());
  57. }
  58. void build(int id, int l , int r){
  59. 	if(l == r){
  60. 		st[id] = a[l];
  61. 	}
  62. 	else{
  63. 		int m = (l + r) / 2;
  64. 		build(id * 2, l, m);
  65. 		build(id * 2 + 1, m + 1, r);
  66. 		st[id] = max(st[2 * id], st[2 * id + 1]);
  67. 	}
  68. }
  69. void update(int id, int l, int r, int i, int val){
  70. 	if(l > i || i > r) return;
  71. 	if(l == r){
  72. 		st[id] =  val;
  73. 		return;
  74. 	}
  75. 	else{
  76. 		int m  = (l + r) / 2;
  77. 		update(2 * id, l, m, i, val);
  78. 		update(2 * id + 1, m + 1, r, i, val);
  79. 		st[id] = max(st[2 * id], st[2 * id + 1]);
  80. 	}
  81. }
  82. int get(int id, int l, int r, int u, int v){
  83. 	int get1 = 0, get2 = 0;
  84. 	if(l > v || u > r) return -INF;
  85. 	if(l >= u && r <= v) return st[id]; // doan [l..r] nam trong doan [u...v]
  86. 	else{
  87. 		int m = (l + r) / 2;
  88. 		get1 = get(2 * id, l, m, u, v);
  89. 		get2 = get(2 * id + 1, m + 1, r , u, v);
  90. 	}
  91. 	return max(get1, get2);
  92. }
  93. void solve(){
  94. //	build(1, 1, n);
  95.     int m = v.size();
  96.     int ans = 0;
  97.     int kq = 0;
  98. 	for(int i = 1; i <= n; i++){
  99.         int pos = lb(all(v), a[i]) - v.begin() + 1;
  100.         int mx = 0;
  101.         if(pos > 1) mx = get(1, 1, m, 1, pos - 1);
  102.         int dp = mx + 1;
  103.         if(ans > dp) kq=1;
  104.         else if(ans == dp) kq++;
  105.         ans = max(ans, dp);
  106.         update(1, 1, m, pos, dp);
  107. 	}
  108. 	cout << kq << nn;
  109. }
  110. signed main() {
  111. 	// freopen("piggyback.in", "r", stdin);
  112. 	// freopen("piggyback.out", "w", stdout);
  113. 	ios_base::sync_with_stdio(0);
  114. 	cin.tie(0);
  115. 	cout.tie(0);
  116.     nhap();
  117.     solve();
  118. 	return 0;
  119.  
  120. }
  121.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
7
1 1 2 2 4 3 3
stdout
copy 
4
https://ideone.com/0p12kn
language:
C++14 (gcc 8.3)
created:
4 hours 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!