#include<iostream>
#define DIM 100005
using namespace std;
static int aib[DIM], nxt[DIM], sum[DIM], pmax[DIM];
static int N;
void update(int x, int val){
x++;
for(; x <= N; x += (x & -x) ){
aib[x] += val;
}
}
int query(int val){
int p, x = 0, sum = 0;
for(p = 17; p >= 0; p--){
if( x + (1 << p) <= N && sum + aib[ x + (1 << p) ] < val){
sum += aib[ x + (1 << p) ];
x += (1 << p);
}
}
return x;
}
int GetBestPosition(int n, int q, int r, int *v, int *s, int *e) {
int i, j, p, u;
N = n;
for(i = 0; i < n; i++){
nxt[i] = i + 1;
update(i, 1);
}
pmax[n + 1] = n + 1;
for(i = n; i >= 1; i--){
pmax[i] = pmax[i + 1];
if(v[i] > r){
pmax[i] = i;
}
}
for(i = 0; i < q; i++){
p = u = query(s[i] + 1);
for(j = 1; j <= e[i] - s[i] + 1; j++){
u = nxt[u];
}
int aux;
for(j = nxt[p]; j != u; j = aux){
aux = nxt[j];
nxt[j] = u;
update(j, -1);
}
nxt[p] = u;
if(pmax[p] >= u - 1){
sum[p]++;
sum[u - 1]--;
}
}
p = 0;
for(i = 1; i < n; i++){
sum[i] += sum[i - 1];
if(sum[p] < sum[i]){
p = i;
}
}
return p;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
452 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
1536 KB |
Output is correct |
2 |
Correct |
59 ms |
3064 KB |
Output is correct |
3 |
Correct |
23 ms |
2296 KB |
Output is correct |
4 |
Correct |
51 ms |
4728 KB |
Output is correct |
5 |
Correct |
50 ms |
4504 KB |
Output is correct |
6 |
Correct |
44 ms |
4088 KB |
Output is correct |
7 |
Correct |
51 ms |
4728 KB |
Output is correct |
8 |
Correct |
52 ms |
4728 KB |
Output is correct |
9 |
Correct |
20 ms |
2808 KB |
Output is correct |
10 |
Correct |
23 ms |
2936 KB |
Output is correct |