#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
const int MAXN = 500100;
const int MAXK = 30;
int n, c,r;
int k[MAXN], s[MAXN], e[MAXN];
ll tree[4*MAXN], lazy[4*MAXN][2];
void shift (int id) {
if (lazy[id][0] != -1) {
ll val = lazy[id][0];
tree[2*id] = val;
tree[2*id+1] = val;
lazy[2*id][0] = lazy[2*id+1][0] = val;
lazy[2*id][1] = lazy[2*id+1][1] = 0;
lazy[id][0] = -1;
}
ll val = lazy[id][1];
tree[2*id] -= val;
tree[2*id+1] -= val;
lazy[2*id][1] += val;
lazy[2*id+1][1] += val;
lazy[id][1] = 0;
}
void upd (int t, int fr, int to, ll val, int id = 1, int le = 0, int ri = n-1) {
if (to < le || fr > ri) return;
if (fr <= le && ri <= to) {
if (t == 0) {
tree[id] = val;
lazy[id][0] = val;
lazy[id][1] = 0;
} else {
tree[id] -= val;
//lazy[id][0] = -1;
lazy[id][1] += val;
}
return;
}
int mid = (le+ri)/2;
shift(id);
upd(t, fr, to, val, 2*id, le, mid);
upd (t, fr, to, val, 2*id+1, mid+1, ri);
tree[id] = min(tree[2*id], tree[2*id+1]);
}
ll get (int p, int id = 1, int le = 0, int ri = n-1) {
if (le == ri) return tree[id];
int mid = (le+ri)/2;
shift(id);
if(p <= mid)
return get(p, 2*id, le, mid);
else
return get(p, 2*id+1, mid+1, ri);
}
int par[MAXN], mn[MAXN], mx[MAXN];
int repr[MAXN];
int find (int a) {return par[a] = par[a]==a ? a : find(par[a]);}
bool same (int a, int b) {return find(a) == find(b);}
void unite (int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
par[b] = a;
mn[a] = max(mn[a], mn[b]);
mx[a] = max(mx[a], mx[b]);
}
int parentInTree[4*MAXN];
vi adj[MAXN];
int dep[MAXN];
int lift[MAXN][MAXK];
int mxDep = 0;
void dfs (int v) {
mxDep = max(mxDep, dep[v]);
FOR(i, 1, MAXK-1)
lift[v][i] = lift[lift[v][i-1]][i-1];
for (int u : adj[v]) {
dep[u] = dep[v]+1;
lift[u][0] = v;
dfs(u);
}
}
int lca (int u, int v) {
if (u == v) return u;
if (dep[u] > dep[v])swap(u,v);
int d = dep[v]-dep[u];
FOR(i, 0, MAXK-1)
if (d&(1<<i))
v = lift[v][i];
if (u == v) return u;
for (int i = MAXK-1; i >= 0; i--) {
if (lift[v][i] != lift[u][i]) {
v = lift[v][i];
u = lift[u][i];
}
}
return lift[v][0];
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n = N;
c = C;
r = R;
FOR(i, 0, n-1) {
k[i] = K[i];
}
FOR(i, 0, c-1) {
s[i] = S[i];
e[i] = E[i];
}
FOR(i, 0, n-1) upd(0, i, i, i);
FOR(i, 0, n-1) {
par[i] = mn[i] = mx[i] = repr[i] = i;
}
FOR(i, 0, c-1) {
int le = 0, ri = n-1;
while (le < ri) {
int mid = (le+ri)/2;
if (get(mid) >= s[i]) ri = mid;
else le = mid+1;
}
int cr = le;
int fr = le, to = le;
vi nodes;
while (cr <= n-1 && get(cr) <= e[i]) {
cr = find(cr);
to = mx[cr];
nodes.pb(cr);
parentInTree[repr[cr]] = n+i;
cr = to+1;
}
int lst = nodes[0];
//for (int k = 1; k < (int)nodes)
for (int x : nodes) unite(lst,x);
repr[find(fr)] = n+i;
upd(0, fr, to, get(fr));
if (to+1 <= n-1) upd(1, to+1, n-1, e[i]-s[i]);
//cout <<" after i=" << i << " round s=" << s[i] << " e=" << e[i] << endl;
//FOR(k, 0, n-1) cout << " curval k=" << k << " val = " << get(k) << endl;
}
// FOR(i, 0, n+c-1) cout << " i = " << i << " par in tree = " << parentInTree[i] << endl;
FOR(i, 0, n+c-2) adj[parentInTree[i]].pb(i);
dfs(n+c-1);
vi wh;
FOR(i, 0, n-2) if (k[i] > r) wh.pb(i);
/* cout << " white: ";
for (int xx : wh) cout << xx << " ";
cout << endl;*/
//if ((int)wh.size() == 0) {
// return mxDep;
// }
int ans = 0;
int ansId = 0;
int whId = -1;
FOR(i, 0, n-1) {
// cout << " i = " << i << endl;
if (whId+1 < (int)wh.size() && wh[whId+1] < i)
whId++;
/// whId - before, whId+1 - after
//cout << " whId = " << whId << endl;
int cur = dep[i];
if (whId >= 0) {
int anc = lca(wh[whId], i);
//cout << " anc wh = " << wh[whId] << " i = " << i << " anc = " << anc << endl;
int dst = dep[i] - dep[anc] - 1;
cur = min(cur, dst);
}
if (whId+1 < (int)wh.size()) {
// cout << " adaasdass" << endl;
//cout << " bef anc wh = " << wh[whId+1]+1 << " i = " << i << endl;
int anc = lca(wh[whId+1]+1, i) ;
//cout << " anc wh = " << wh[whId+1]+1 << " i = " << i << " anc = " << anc << endl;
int dst = dep[i] - dep[anc] - 1;
cur = min(cur, dst);
}
//cout << " i = " << i << " cur = " << cur << endl;
if (cur > ans) {
ans = cur;
ansId = i;
}
}
return ansId;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
12108 KB |
Output is correct |
| 2 |
Correct |
8 ms |
12140 KB |
Output is correct |
| 3 |
Correct |
10 ms |
12260 KB |
Output is correct |
| 4 |
Correct |
10 ms |
12236 KB |
Output is correct |
| 5 |
Correct |
9 ms |
12124 KB |
Output is correct |
| 6 |
Correct |
10 ms |
12320 KB |
Output is correct |
| 7 |
Correct |
10 ms |
12284 KB |
Output is correct |
| 8 |
Correct |
10 ms |
12304 KB |
Output is correct |
| 9 |
Correct |
9 ms |
12236 KB |
Output is correct |
| 10 |
Correct |
10 ms |
12240 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
12440 KB |
Output is correct |
| 2 |
Correct |
31 ms |
14336 KB |
Output is correct |
| 3 |
Correct |
14 ms |
13344 KB |
Output is correct |
| 4 |
Correct |
25 ms |
14148 KB |
Output is correct |
| 5 |
Correct |
23 ms |
14156 KB |
Output is correct |
| 6 |
Correct |
22 ms |
13772 KB |
Output is correct |
| 7 |
Correct |
31 ms |
14332 KB |
Output is correct |
| 8 |
Correct |
31 ms |
14284 KB |
Output is correct |
| 9 |
Correct |
15 ms |
13260 KB |
Output is correct |
| 10 |
Correct |
30 ms |
14148 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
196 ms |
28280 KB |
Output is correct |
| 2 |
Correct |
563 ms |
57544 KB |
Output is correct |
| 3 |
Correct |
148 ms |
35648 KB |
Output is correct |
| 4 |
Correct |
504 ms |
53876 KB |
Output is correct |
| 5 |
Correct |
513 ms |
53956 KB |
Output is correct |
| 6 |
Correct |
460 ms |
45180 KB |
Output is correct |
| 7 |
Correct |
517 ms |
55072 KB |
Output is correct |
| 8 |
Correct |
522 ms |
55036 KB |
Output is correct |
| 9 |
Correct |
120 ms |
35184 KB |
Output is correct |
| 10 |
Correct |
155 ms |
35652 KB |
Output is correct |
