#include <bits/stdc++.h>
#define gc getchar_unlocked
inline void getint(int &x){
int c = gc();
x = 0;
for(;(c<48 || c>57);c = gc());
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}
inline void print(int n)
{
if (n == 0)
{
putchar_unlocked('0');
putchar_unlocked('\n');
}
else if (n == -1)
{
putchar_unlocked('-');
putchar_unlocked('1');
putchar_unlocked('\n');
}
else
{
char buf[11];
buf[10] = '\n';
int i = 9;
while (n)
{
buf[i--] = n % 10 + '0';
n /= 10;
}
while (buf[i] != '\n')
putchar_unlocked(buf[++i]);
}
}
using namespace std;
const int MAXN = 500010;
int BUCKET;
vector<int> maiores,minpos,maxpos;
int vetor[MAXN],N,raizes[MAXN];
int main(){
getint(N);
BUCKET = (int)ceil(sqrt(N));
int atual = 0;
for(int i = 1;i<=N;i++){
getint(vetor[i]);
maiores.push_back(vetor[i]);
if(atual * atual < i) atual++;
raizes[i] = atual;
}
sort(maiores.begin(),maiores.end());
maiores.erase(unique(maiores.begin(),maiores.end()),maiores.end());
reverse(maiores.begin(),maiores.end());
while(maiores.size() >= BUCKET) maiores.pop_back();
reverse(maiores.begin(),maiores.end());
minpos.assign(maiores.size(),MAXN);
maxpos.assign(maiores.size(),1);
for(int i = 1;i<=N;i++){
int idx = lower_bound(maiores.begin(),maiores.end(),vetor[i]) - maiores.begin();
if(maiores[idx] != vetor[i]) continue;
minpos[idx] = min(minpos[idx],i);
maxpos[idx] = max(maxpos[idx],i);
}
for(int i = 1;i<=N;i++){
int p = 0;
for(int j = 0;j<maiores.size();j++){
int davez = raizes[max(abs(i - minpos[j]),abs(i - maxpos[j]))] + (maiores[j] - vetor[i]);
p = max(p,davez);
}
print(p);
}
return 0;
}
Compilation message
pio.cpp: In function 'int main()':
pio.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(maiores.size() >= BUCKET) maiores.pop_back();
^
pio.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<maiores.size();j++){
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
1256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
1688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
1760 KB |
Output is correct |
2 |
Correct |
6 ms |
1760 KB |
Output is correct |
3 |
Correct |
63 ms |
1880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
2280 KB |
Output is correct |
2 |
Correct |
14 ms |
2280 KB |
Output is correct |
3 |
Correct |
141 ms |
2780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
458 ms |
4636 KB |
Output is correct |
2 |
Correct |
33 ms |
4636 KB |
Output is correct |
3 |
Correct |
505 ms |
5072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
954 ms |
8332 KB |
Output is correct |
2 |
Correct |
48 ms |
8332 KB |
Output is correct |
3 |
Execution timed out |
1002 ms |
8336 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1073 ms |
9808 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1079 ms |
9808 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |