fork(1) download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<fstream>
  4. #include<climits>
  5. #include<iomanip>
  6. #include<vector>
  7. #define fr(i, zz, zzz) for (int i = zz; i <= zzz; i++)
  8. #define ll long long
  9. #define pii pair<int, int>
  10. #define frr(i, zz, zzz) for (int i = zz; i >= zzz; i--)
  11. #define full(asdf) memset(asdf, 0, sizeof(asdf))
  12. #define st first
  13. #define nd second
  14. #define IOS ios_base::sync_with_stdio(0);   cin.tie(0); cout.tie(0);
  15. using namespace std;
  16. const int N = 1E5 + 10;
  17. fstream f, g;
  18. int n, Q, k, val;
  19. pii a[N];
  20. int cnt = 0, mx = 0;
  21. pii vmax[N];
  22.  
  23. bool cmp (pii a, pii b) {
  24. 	return a.st < b.st || (a.st == b.st && a.nd > b.nd);
  25. }
  26. void open(string s) {
  27. 	string in = s + ".INP", out = s + ".OUT";
  28. 	f.open(in, ios::in);
  29. 	g.open(out, ios::out);
  30. }
  31. void close() {
  32. 	f.close();
  33. 	g.close();
  34. }
  35.  
  36. void input() {
  37. 	f >> n >> Q;
  38. 	fr(i, 1, n)
  39. 		f >> a[i].st;
  40. }
  41.  
  42. int binary() {
  43. 	int l = 0, r = k;
  44. 	while ( l <= r) {
  45. 		int m = (l + r) >> 1;
  46. 		if (vmax[m].st < val)
  47. 			l = m + 1;
  48. 		else if (vmax[m].st >= val)
  49. 			r = m - 1;
  50. 	}
  51. 	return l;
  52. }
  53.  
  54. void pre_solve() {
  55. 	int l[N], r[N];
  56. 	fr(i, 1, n) {
  57. 		l[i] = i - 1;
  58. 		while(l[i] > 0 && a[l[i]].st <= a[i].st)
  59. 			l[i] = l[l[i]];
  60.  
  61. 	}
  62. 	frr(i, n, 1) {
  63. 		r[i] = i + 1;
  64. 		while (r[i] <= n && a[r[i]].st <= a[i].st)
  65. 			r[i] = r[r[i]];
  66. 	}
  67.  
  68. 	fr(i, 1, n) 
  69. 		a[i].nd = r[i] - l[i] - 1;
  70.  
  71. 	sort(a+1, a+n+1, cmp);
  72. 	cnt = a[1].nd;
  73. 	fr(i, 1, n) {
  74. 		if (a[i].st == a[i+1].st)
  75. 			cnt = max({cnt, a[i].nd, a[i+1].nd});
  76. 		else {
  77. 			vmax[++k] = {a[i].st, cnt};
  78. 			cnt = a[i+1].nd;
  79. 		}
  80. 	}
  81. 	int res = 0;
  82. 	fr(i, 1, k)
  83. 		vmax[i].nd = max(vmax[i - 1].nd, vmax[i].nd);
  84. //	fr(i, 1, k)
  85. //		cout << vmax[i].st << " " << vmax[i].nd << "\n";
  86.  
  87. }
  88.  
  89. int solve() {
  90. 	int m = binary();
  91. 	if (vmax[m].st > val)
  92. 		--m;
  93. //	cout << vmax[m] << "\n";
  94. 	return vmax[m].nd;
  95. }
  96.  
  97. int main () {
  98. 	IOS
  99. 	open("CPACK");
  100. 	input();
  101. 	pre_solve();
  102. 	int res;
  103. 	vmax[k+1].st = 2000000000;
  104. 	while (Q--) {
  105. 		f >> val;
  106. 		g << solve() << "\n";
  107. 	}
  108. 	close();
  109. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yTtg70
Bài 3 HSG 10 Tin Hà Tĩnh 2023-2024
language:
C++14 (gcc 8.3)
created:
53 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!