fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<int,int> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef set<int>::iterator sit;
  20. typedef map<int,int>::iterator mit;
  21. typedef vector<int>::iterator vit;
  22.  
  23. const int MOD = 1e9 + 7;
  24. const int N = 300010;
  25.  
  26. int a[N];
  27.  
  28. struct node
  29. {
  30. 	int len; ll cnt;
  31. };
  32.  
  33. node st[2][N*4];
  34.  
  35. void combine(int type, int id)
  36. {
  37. 	int l = id*2; int r = (l^1);
  38. 	if(st[type][l].len>st[type][r].len)
  39. 	{
  40. 		st[type][id] = st[type][l];
  41. 	}
  42. 	else if(st[type][l].len<st[type][r].len)
  43. 	{
  44. 		st[type][id] = st[type][r];
  45. 	}
  46. 	else
  47. 	{
  48. 		st[type][id] = st[type][l];
  49. 		st[type][id].cnt = (st[type][r].cnt + st[type][id].cnt)%MOD;
  50. 	}
  51. }
  52.  
  53. int n; 
  54.  
  55. void build(int type, int id = 1, int l = 0, int r = n)
  56. {
  57. 	if(r - l < 2)
  58. 	{
  59. 		st[type][id].len = -1;
  60. 		st[type][id].cnt = 0;
  61. 		return ;
  62. 	}
  63. 	int mid = (l+r)>>1;
  64. 	build(type,id*2,l,mid);
  65. 	build(type,id*2+1,mid,r);
  66. 	combine(type, id);
  67. }
  68.  
  69. void update(int type, int id, int l, int r, int pos, int mx, int cnt)
  70. {	
  71. 	if(pos<l||pos>=r) return ;
  72. 	if(r - l < 2)
  73. 	{
  74. 		st[type][id].cnt = cnt;
  75. 		st[type][id].len = mx;
  76. 		return ;
  77. 	}
  78. 	int mid = (l+r)>>1;
  79. 	update(type,id*2,l,mid,pos,mx,cnt);
  80. 	update(type,id*2+1,mid,r,pos,mx,cnt);
  81. 	combine(type,id);
  82. }
  83.  
  84. ii query(int type, int id, int l, int r, int ql, int qr)
  85. {
  86. 	if(qr<=l||r<=ql) return mp(-1, 0);
  87. 	if(ql<=l&&r<=qr) return mp(st[type][id].len, st[type][id].cnt);
  88. 	int mid = (l+r)>>1;
  89. 	ii L = query(type,id*2, l, mid, ql, qr);
  90. 	ii R = query(type,id*2+1, mid, r, ql, qr);
  91. 	if(L.fi>R.fi) return L;
  92. 	else if(L.fi<R.fi) return R;
  93. 	else return (mp(L.fi, (L.se+R.se)%MOD));
  94. }
  95.  
  96. int main()
  97. {
  98. 	ios_base::sync_with_stdio(0); cin.tie(0);
  99. 	cin >> n;
  100. 	for(int i = 0; i < n; i++)
  101. 	{
  102. 		cin>>a[i]; a[i]--;
  103. 	}
  104. 	build(0); build(1);
  105. 	ll ans = 0; ll bestans = -1;
  106. 	ll ans1 = 0; ll bestans1 = -1;
  107. 	for(int i = 0; i < n; i++)
  108. 	{
  109. 		ii tmp1 = query(1, 1, 0, n, a[i] + 1, n + 1);
  110. 		ii tmp0 = query(0, 1, 0, n, 0, a[i]);
  111. 		if(tmp1.fi == -1) 
  112. 		{
  113. 			tmp1 = mp(0, 1);
  114. 		}
  115. 		if(tmp0.fi == -1)
  116. 		{
  117. 			tmp0 = mp(0, 1);
  118. 		}
  119. 		if(tmp1.fi + 1 > bestans)
  120. 		{
  121. 			bestans = tmp1.fi + 1;
  122. 			ans = tmp1.se;
  123. 		}
  124. 		else if(tmp1.fi + 1 == bestans)
  125. 		{
  126. 			ans = (ans + tmp1.se)%MOD;
  127. 		}
  128. 		if(tmp0.fi + 1 > bestans1)
  129. 		{
  130. 			bestans1 = tmp0.fi + 1;
  131. 			ans1 = tmp0.se;
  132. 		}
  133. 		else if(tmp0.fi + 1 == bestans1)
  134. 		{
  135. 			ans1 = (ans1 + tmp0.se)%MOD;
  136. 		}
  137. 		update(1, 1, 0, n, a[i], tmp0.fi+1, tmp0.se);
  138. 		update(0, 1, 0, n, a[i], tmp1.fi+1, tmp1.se);
  139. 	}
  140. 	if(bestans>bestans1)
  141. 	{
  142. 		cout << bestans << ' ' << ans << '\n';
  143. 	}
  144. 	else if(bestans<bestans1)
  145. 	{
  146. 		cout << bestans1 << ' ' << ans1 << '\n';
  147. 	}
  148. 	else
  149. 	{
  150. 		cout << bestans << ' ' << (ans+ans1)%MOD << '\n';
  151. 	}
  152. }
  153.  
Success #stdin #stdout 0s 32768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1 0
https://ideone.com/c18DLb
language:
C++14 (gcc 8.3)
created:
7 years 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!