#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 11;
struct BIT{
int bit[MAXN] = {};
void add(int p, int v){
++p; for(int i = p; i < MAXN; i += i & -i) bit[i] += v;
}
int qry(int p){
++p; int r = 0; for(int i = p; i; i -= i & -i) r += bit[i];
return r;
}
int bs(int v){
int p = 0, s = 0; for(int j = 19; j >= 0; j--) if(p + (1 << j) < MAXN && s + bit[p + (1 << j)] <= v) s += bit[p + (1 << j)], p += (1 << j);
return p;
}
} bit;
struct ST{
int st[20][MAXN];
void init(int N, int *K){
for(int i = 0; i < N; i++) st[0][i] = K[i];
for(int j = 1; j < 20; j++){
for(int i = 0; i <= N - (1 << j); i++){
st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
}
int qry(int l, int r){
assert(l <= r);
int d = __lg(r - l + 1);
return max(st[d][l], st[d][r - (1 << d) + 1]);
}
} RMQ;
bool isMax(int i, int R, int l, int r){
assert(l <= i && i <= r);
return R > RMQ.qry(l, r - 1);
}
struct update{
int p, c, t;
};
struct range{
int l, r, l2, r2, t;
bool include(int i){
return l <= i && i <= r;
}
bool can(int i, int R){
return !(l2 <= i && i <= r2) || R > RMQ.qry(l2, r2 - 1);
}
};
range operator+ (const range& a, const range& b){
if(a.t == 0 || b.t == 0) return a.t == 0 ? b : a;
return {min(a.l, b.l), max(a.r, b.r), a.l2, a.r2, a.t + b.t};
}
int C;
struct SegTree{
range t[MAXN << 2];
void init(int *S, int *E, int v = 0, int l = 0, int r = C - 1){
if(l == r) t[v] = {S[l], E[l], S[l], E[l], 0};
else{
int m = (l + r) / 2;
init(S, E, v * 2 + 1, l, m);
init(S, E, v * 2 + 2, m + 1, r);
t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}
}
void enable(int p, int a, int v = 0, int l = 0, int r = C - 1){
if(l == r) t[v].t = a;
else{
int m = (l + r) / 2;
if(p <= m) enable(p, a, v * 2 + 1, l, m);
else enable(p, a, v * 2 + 2, m + 1, r);
t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}
}
int left(int i, int v = 0, int l = 0, int r = C - 1){
if(l == r){
if(t[v].include(i)) return l;
else return -1;
}else{
int m = (l + r) / 2;
if(t[v * 2 + 1].include(i)) return left(i, v * 2 + 1, l, m);
else return left(i, v * 2 + 2, m + 1, r);
}
}
int right(int i, int R, int v = 0, int l = 0, int r = C - 1){
if(l == r){
if(t[v].can(i, R)) return l;
else return -1;
}else{
int m = (l + r) / 2;
if(t[v * 2 + 2].can(i, R)) return right(i, R, v * 2 + 2, m + 1, r);
else return right(i, R, v * 2 + 1, l, m);
}
}
int sum(int qr, int v = 0, int l = 0, int r = C - 1){
if(l == r) return qr >= l ? t[v].t : 0;
else{
int m = (l + r) / 2;
if(qr <= m) return sum(qr, v * 2 + 1, l, m);
else return t[v * 2 + 1].t + sum(qr, v * 2 + 2, m + 1, r);
}
}
} st;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
::C = C;
for(int i = 0; i < N; i++) bit.add(i, 1);
for(int i = 0; i < C; i++){
int l = S[i] == 0 ? 0 : bit.bs(S[i] - 1) + 1;
int r = bit.bs(E[i]);
for(int j = E[i] - 1; j >= S[i]; j--){
bit.add(bit.bs(j), -1);
}
S[i] = l, E[i] = r;
}
RMQ.init(N, K);
st.init(S, E);
int mx = -1, ans = -1;
vector<update> U; int uid = 0;
for(int i = 0; i < C; i++){
U.push_back({S[i], i, 1});
U.push_back({E[i] + 1, i, 0});
}
sort(U.begin(), U.end(), [](update a, update b){
return a.p < b.p;
});
for(int i = 0; i < N; i++){
while(uid < C * 2 && U[uid].p <= i) st.enable(U[uid].c, U[uid].t), uid++;
int l = st.left(i), r = st.right(i, R);
int res = st.sum(r) - st.sum(l - 1);
if(res > mx){
mx = res;
ans = i;
}
}
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1324 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
708 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
44 ms |
6224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
