#include<algorithm>
using namespace std;
const int idx = 1<<17;
int T[1<<18];
void update(int a,int b,int item)
{
a+=idx,b+=idx;
while(a<=b){
if(a&1)T[a]+=item;
if((b&1)==0)T[b]+=item;
a=(a+1)>>1, b=(b-1)>>1;
}
}
int read1(int x)
{
int ret=0;
x+=idx;
while(x)ret+=T[x],x>>=1;
return ret;
}
int read2(int a,int b)
{
a+=idx,b+=idx;
int ret = 0;
while(a<=b){
ret=max(ret,T[a]);
ret=max(ret,T[b]);
a = (a+1)>>1, b = (b-1)>>1;
}
return ret;
}
int sum[100010],ans;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
int i;
for(i=0;i<C;i++){
int s = read1(S[i]-1) + S[i];
int e = read1(E[i]) + E[i];
update(s,N,E[i]-S[i]);
S[i]=s,E[i]=e;
}
for(i=0;i<N;i++)T[i+idx]=K[i];
for(i=idx-1;i;i--)T[i]=max(T[i<<1],T[i<<1|1]);
for(i=0;i<C;i++){
int s = read2(S[i],E[i]-1);
if(s<R)sum[S[i]]++,sum[E[i]+1]--;
}
for(i=0;i<N;i++)sum[i]+=sum[i-1];
for(i=0;i<N;i++)ans=max(ans,sum[i]);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2500 KB |
Output is correct |
2 |
Incorrect |
0 ms |
2500 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2500 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
20 ms |
2944 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |