이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int DIM = 1e5 + 5;
int n, nr;
int h[2 * DIM];
int tt[2 * DIM][20], mx[DIM][20];
vector <int> v[2 * DIM];
int sum[4 * DIM], arb[4 * DIM];
void build(int st = 0, int dr = n - 1, int nod = 1) {
if (st == dr) {arb[nod] = st; sum[nod] = 1; return ;}
int mij = (st + dr) / 2;
build(st, mij, nod * 2);
build(mij + 1, dr, nod * 2 + 1);
sum[nod] = sum[nod * 2] + sum[nod * 2 + 1];
}
void update(int pos, int x, int y, int st = 0, int dr = n - 1, int nod = 1) {
if (st == dr) {arb[nod] = x; sum[nod] += y; return ;}
int mij = (st + dr) / 2;
if (pos <= mij) update(pos, x, y, st, mij, nod * 2);
else update(pos, x, y, mij + 1, dr, nod * 2 + 1);
sum[nod] = sum[nod * 2] + sum[nod * 2 + 1];
}
pair <int, int> find(int pos, int st = 0, int dr = n - 1, int nod = 1) {
if (st == dr) return {arb[nod], st};
int mij = (st + dr) / 2;
if (pos <= sum[nod * 2]) return find(pos, st, mij, nod * 2);
return find(pos - sum[nod * 2], mij + 1, dr, nod * 2 + 1);
}
void dfs(int nod) {
for (auto it : v[nod]) {
h[it] = h[nod] + 1;
tt[it][0] = nod;
// cerr << nod << " " << it << endl;
dfs(it);
}
}
int find_left(int pos, int val) {
for (int k = 19; k >= 0 ; --k) {
if (pos - (1 << k) < 0) continue ;
if (mx[pos - (1 << k)][k] <= val) pos -= (1 << k);
}
return pos;
}
int find_right(int pos, int val) {
for (int k = 19; k >= 0 ; --k) {
if (pos + (1 << k) > n - 1) continue ;
if (mx[pos][k] <= val) pos += (1 << k);
}
return pos;
}
int get_lca(int x, int y, bool wh) {
if (h[x] < h[y]) swap(x, y), wh = 1 - wh;
int ans = 0;
if (wh) ans = h[x] - h[y];
int dif = h[x] - h[y], k = 19;
while (dif > 0) {
if (dif & (1 << k)) {
dif = dif ^ (1 << k);
x = tt[x][k];
}
--k;
}
for (int k = 19; k >= 0 ; --k) {
if (tt[x][k] != tt[y][k]) {
x = tt[x][k]; y = tt[y][k];
ans = ans + (1 << k);
}
}
return ans + 1;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n = N;
nr = n - 1;
build();
for (int i = 0; i < C ; ++i) {
++nr;
for (int j = E[i]; j >= S[i] ; --j) {
pair <int, int> x = find(j + 1);
v[nr].push_back(x.first);
update(x.second, 0, -1);
}
update(S[i], nr, 1);
}
dfs(nr);
for (int i = 0; i < n - 1 ; ++i) mx[i][0] = K[i];
for (int k = 1; k <= 19 ; ++k) {
for (int i = 0; i < nr ; ++i) {
tt[i][k] = tt[tt[i][k - 1]][k - 1];
for (int i = 0; i < n - 1 ; ++i) {
if (i + (1 << (k - 1)) < n - 1)
mx[i][k] = max(mx[i][k - 1], mx[i + (1 << (k - 1))][k - 1]);
else
mx[i][k] = mx[i][k - 1];
}
}
}
int sol = 0;
for (int i = 0; i < n ; ++i) {
int l = find_left(i - 1, R);
if (l >= 0 && K[l] <= R) --l;
int r = find_right(i, R);
if (r < n - 1 && K[r] <= R) ++r;
++r;
int ans = C;
if (l >= 0) ans = min(ans, get_lca(l, i, 0));
if (r < n - 1) ans = min(ans, get_lca(r, i, 0));
sol = max(sol, ans);
}
return sol - 1;
}
/**
5 3 3
1
0
2
4
1 3
0 1
0 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... |