// late knights in the middle of june...
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define mp make_pair
#define fi first
#define se second
#define lsb(x) ((x) & (-x))
const int MAXN = 100005;
int fw1[MAXN];
int fw2[MAXN];
void update(int *fw, int X, int V){
X++;
while(X<MAXN){
fw[X] += V;
X += lsb(X);
}
}
int query(int *fw, int R){
R++;
if(R==0) return 0;
int result = 0;
while(R){
result += fw[R];
R -= lsb(R);
}
return result;
}
int fbs(int *fw, int V){
int pos=0;
int cs=0;
for(int x=16; x>=0; x--){
if(pos+(1<<x) >= MAXN) continue;
if(cs + fw[pos+(1<<x)] < V){
pos += 1<<x;
cs += fw[pos];
}
}
return pos;
}
struct node{
int s, e, m;
int val;
node *l, *r;
node(int S, int E){
s = S, e = E, m = (s+e)/2;
val = 0;
if(s != e){
l = new node(s, m);
r = new node(m+1, e);
}
}
void update(int X, int V){
if(s == X && e == X){
val = V;
}
else{
if(X <= m) l->update(X, V);
else r->update(X, V);
val = max(l->val, r->val);
}
}
int query(int S, int E){
if(s == S && e == E) return val;
else if(E<=m) return l->query(S, E);
else if(S>m) return r->query(S, E);
else return max(l->query(S, m), r->query(m+1, E));
}
} *root;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
cerr << '\n';
memset(fw1, 0, sizeof(fw1));
for(int i=1; i<=N; i++){
update(fw1, i, 1);
}
pii q[C];
for(int i=0; i<C; i++){
int rs = fbs(fw1, S[i]);
int re = fbs(fw1, E[i]+1)-1;
q[i] = mp(rs, re);
int ts;
while((ts = fbs(fw1, rs+1)) <= re){
update(fw1, ts, -1);
}
cerr << rs << ' ' << re << '\n';
}
root = new node(0, N-2);
for(int i=0; i<N-1; i++){
root->update(i, K[i]);
}
memset(fw2, 0, sizeof(fw2));
for(int i=0; i<C; i++){
int cmax = root->query(q[i].fi, q[i].se-1);
if(cmax < R){
update(fw2, q[i].fi, 1);
update(fw2, q[i].se+1, -1);
}
}
int cmax=0, P=0;
for(int i=0; i<N; i++){
// int temp = query(fw2, i);
int temp = 0;
for(int j=0; j<C; j++){
if(i >= q[j].fi && i <= q[j].se && root->query(q[j].fi, q[j].se-1) < R){
temp++;
}
}
cerr << temp << ' ';
if(temp > cmax){
cmax = temp;
P = i;
}
}
cerr << '\n';
return P;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1079 ms |
6844 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
