#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int fw[MAXN], nums;
void fupdate(int p, int v){
while (p <= nums){
fw[p] += v;
p += (p & (-p));
}
}
int fquery(int p){
int ans = 0;
while (p){
ans += fw[p];
p -= (p & (-p));
}
return ans;
}
struct node{
int s, e, m, val, lazy;
node *l, *r;
node (int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1, val = 0, lazy = 0;
if (s != e){
l = new node(s, m);
r = new node(m + 1, e);
}
}
void push(int v){
val += v; lazy += v;
}
void propo(){
if (s == e) return;
if (lazy != 0){
l->push(lazy); r->push(lazy);
lazy = 0;
}
}
void update(int x, int y, int v){
if (s == e){
push(v); return;
}
propo();
if (y <= m) l->update(x, y, v);
else if (x > m) r->update(x, y, v);
else{
l->update(x, m, v); r->update(m + 1, y, v);
}
propo();
val = max(l->val, r->val);
}
int query(int x, int y){
if (x == s && y == e) return val;
propo();
if (y <= m) return l->query(x, y);
else if (x > m) return r->query(x, y);
else return max(l->query(x, m), r->query(m + 1, y));
}
int qind(){
if (s == e) return s;
propo();
if (l->val >= r->val) return l->qind();
else return r->qind();
}
};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
nums = N;
set<int> spos;
for (int i = 1; i <= nums; i++){
fupdate(i, 1);
spos.insert(i);
}
spos.insert(nums + 1);
vector<pair<int, int>> rcoords(C);
for (int i = 0; i < C; i++){
int s = S[i], e = E[i], l = 1, r = nums, rs, re;
s++; e++;
while (l <= r){
int m = (l + r) >> 1;
if (fquery(m) >= s){
rs = m;
r = m - 1;
}
else l = m + 1;
}
auto it = spos.lower_bound(rs); it++;
for (int j = s + 1; j <= e; j++, it++) fupdate(*it, -1);
re = (*it) - 1;
rcoords[i] = {rs, re};
}
node *root = new node(1, nums - 1), *root2 = new node(1, nums);
for (int i = 1; i < nums; i++) root->update(i, i, K[i - 1]);
for (auto &[s, e] : rcoords)
if (root->query(s, e - 1) < R)
root2->update(s, e, 1);
return root2->qind() - 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
12916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
