#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef pair<int, int> ii;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n;
int a[N], tmp[N];
int check(int k)
{
int res = 0;
for(int i = 1; i <= n; i++)
tmp[i] = (a[i] > k);
for(int i = 1; i <= n + 1; i++)
res += (tmp[i] == 0 && tmp[i - 1] == 1);
return res;
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
int l = 0, r = 2e9, res = 0;
while(r - l >= 3)
{
int midl = l + (r - l) / 3;
int midr = r - (r - l) / 3;
if(check(midl) >= check(midr))
r = midr;
else
l = midl;
}
for(int i = l; i <= r; i++) res = max(res, check(i));
l = 0, r = 2e9;
while(r - l >= 3)
{
int midl = l + (r - l) / 3;
int midr = r - (r - l) / 3;
if(check(midl) > check(midr))
r = midr;
else
l = midl;
}
for(int i = l; i <= r; i++) res = max(res, check(i));
cout << res;
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
1048 KB |
Output is correct |
2 |
Correct |
41 ms |
1108 KB |
Output is correct |
3 |
Correct |
47 ms |
1108 KB |
Output is correct |
4 |
Correct |
41 ms |
1108 KB |
Output is correct |
5 |
Correct |
42 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
74 ms |
1108 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
810 ms |
8128 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
789 ms |
8132 KB |
Output is correct |
2 |
Incorrect |
791 ms |
8124 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |