This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
const int MAXN = 1e5 + 5;
int a[MAXN];
pair<int, int> b[MAXN];
int par[MAXN];
namespace ST {
int N;
int tree[1 << 20];
int act[1 << 20];
void build(int id, int l, int r) {
if(l == r) {
tree[id] = a[r];
act[id] = 1;
return;
}
int m = (l + r) / 2;
build(id * 2, l, m);
build(id * 2 + 1, m + 1, r);
tree[id] = max(tree[id * 2], tree[id * 2 + 1]);
act[id] = act[id * 2] + act[id * 2 + 1];
}
void init(int _N) {
N = _N;
build(1, 1, N);
}
int get_max(int id, int l, int r, int u, int v) {
if(r < u or l > v) return 0;
if(u <= l and r <= v) return tree[id];
int m = (l + r) / 2;
return max(get_max(id * 2, l, m, u, v), get_max(id * 2 + 1, m + 1, r, u, v));
}
int get_max(int l, int r) {
return get_max(1, 1, N, l, r);
}
void update(int id, int l, int r, int u, int v) {
if(r < u or l > v) return;
if(u <= l and r <= v) {
act[id] = 0;
return;
}
int m = (l + r) / 2;
update(id * 2, l, m, u, v);
update(id * 2 + 1, m + 1, r, u, v);
act[id] = act[id * 2] + act[id * 2 + 1];
}
void update(int l, int r) {
return update(1, 1, N, l, r);
}
int walk(int x) {
int id = 1, l = 1, r = N;
while(l < r) {
int m = (l + r) / 2;
if(act[id * 2] >= x) {
id = id * 2;
r = m;
} else {
x = x - act[id * 2];
id = id * 2 + 1;
l = m + 1;
}
}
assert(l == r);
return r;
}
}
int GetBestPosition(int N, int M, int K, int A[], int S[], int E[]) {
for(int i = 0; i < N - 1; i++) a[i + 1] = ++A[i];
for(int i = 0; i < M; i++) {
b[i] = {++S[i], ++E[i]};
}
K++;
vector<pair<int, int>> c;
ST::init(N);
for(int i = 1; i <= M; i++) {
auto [l, r] = b[i];
l = ST::walk(l);
r = ST::walk(r);
par[l] = r = par[r];
ST::update(l + 1, r);
if(K > ST::get_max(l, r - 1)) {
c.emplace_back(l, 1);
c.emplace_back(r, -1);
}
}
sort(c.begin(), c.end(), [&](pair<int, int> a, pair<int, int> b) {
if(a.first != b.first) return a.first < b.first;
return a.second > b.second;
});
int cur = 0;
pair<int, int> ans = {0, 1};
for(auto [p, x] : c) {
cur += x;
if(maximize(ans.first, cur))
ans.second = p;
}
return ans.second - 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |