#include<algorithm>
using namespace std;
#define SZ 131072
int IT[SZ + SZ + 2], IT2[SZ + SZ + 2], Sum[101000];
void Add(int a, int b){
a += SZ;
IT[a] = b;
while (a != 1){
a >>= 1;
IT[a] = max(IT[a * 2], IT[a * 2 + 1]);
}
}
void Add2(int a, int b){
a += SZ;
while (a){
IT2[a] += b; a >>= 1;
}
}
int Max(int b, int e){
b += SZ, e += SZ;
int r = 0;
while (b <= e){
r = max(r, IT[b]);
r = max(r, IT[e]);
b = (b + 1) >> 1, e = (e - 1) >> 1;
}
return r;
}
int Find(int a){
int nd = 1;
while (nd < SZ){
nd *= 2;
if (IT2[nd] < a){
a -= IT2[nd];
nd++;
}
}
return nd - SZ;
}
int Next(int a){
a += SZ;
while (!IT2[a]){
a = (a + 1) >> 1;
}
while (a < SZ){
a *= 2;
if (!IT2[a])a++;
}
return a - SZ;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int i, b, e, M = 0, r = 0;
for (i = 0; i < N - 1; i++)Add(i, K[i]);
for (i = 0; i <= N; i++)Add2(i, 1);
for (i = 0; i < C; i++){
b = Find(S[i] + 1), e = Find(E[i] + 2) - 1;
if (Max(b, e - 1) < R) Sum[b]++, Sum[e + 1]--;
while (1){
b = Next(b + 1);
if (b>e)break;
Add2(b, -1);
}
}
for (i = 0; i < N; i++){
M += Sum[i];
if (r < M)r = M;
}
return r;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3524 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
3524 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
3524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
3968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
