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 pii = pair<int, int>;
const int N = 100010;
const int LN = 18;
int n, ptr[N], nxt[N], ft[N];
int get(int x) {
++x;
int i = 0, c = 0;
for (int j = LN-1; j >= 0; --j) {
int ni = i+(1<<j);
if (ni <= n && ni-(c+ft[ni]) < x) {
i = ni;
c += ft[ni];
}
}
return i;
}
int skip(int x) {
if (nxt[x] == x) return x;
return nxt[x] = skip(nxt[x]);
}
void upd(int i) {
nxt[i] = i+1;
for (++i; i <= n; i += i&-i)
ft[i] += 1;
}
int cnt;
vector<int> G[N*2];
int in[N*2], out[N*2], tick, par[N*2][LN], seg[N*4], dep[N*2];
void dfs(int u, int p)
{
dep[u] = dep[p]+1;
in[u] = tick++;
par[u][0] = p;
for (int i = 1; i < LN; ++i)
par[u][i] = par[par[u][i-1]][i-1];
for (auto v : G[u])
dfs(v, u);
out[u] = tick;
}
void updseg(int p, int x)
{
for (seg[p += cnt] = x; p > 1; p >>= 1)
seg[p>>1] = max(seg[p], seg[p^1]);
}
int getmax(int l, int r)
{
int ans = 0;
for (l += cnt, r += cnt; l < r; l >>= 1, r >>= 1) {
if (l&1) ans = max(ans, seg[l++]);
if (r&1) ans = max(ans, seg[--r]);
}
return ans;
}
int trylift(int s, int r)
{
int u = s;
for (int i = LN-1; i >= 0; --i) {
int v = par[u][i];
if (getmax(in[v], out[v]) == r)
u = v;
}
return dep[s]-dep[u];
}
int GetBestPosition(int n, int c, int r, int *K, int *S, int *E)
{
::n = n;
cnt = n;
for (int i = 0; i < n; ++i)
ptr[i] = i, nxt[i] = i;
nxt[n] = n;
for (int i = 0; i < c; ++i) {
int s = get(S[i]);
int e = get(E[i]);
for (int j = s; j <= e; j = skip(j)) {
G[cnt].push_back(ptr[j]);
if (j != s) {
ptr[j] = -1;
upd(j);
} else {
++j;
}
}
ptr[s] = cnt++;
}
dfs(cnt-1, cnt-1);
updseg(in[0], r);
for (int i = 0; i < n-1; ++i)
updseg(in[i+1], K[i]);
pii ans(trylift(0, r), 0);
for (int i = 1; i < n; ++i) {
updseg(in[i], r);
updseg(in[i-1], K[i-1]);
ans = max(ans, pii(trylift(i, r), i));
}
return ans.first;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |