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>
#define z exit(0)
#define mp make_pair
#define F first
#define S second
using namespace std;
using pii = pair<int,int>;
const int N = 1e5 + 5;
int bit[N], p[N<<1], LOG, up[N][20], dep[N];
pii inter[N], val[N<<1];
void upd(int i, int val){ for(++i; i<N; i+=i&-i) bit[i] += val;}
int pos(int k){
int i = 0, sum = 0;
for(int j = LOG-1; j>=0; --j){
if(i+(1<<j) < N && sum + bit[i+(1<<j)] < k) sum += bit[i+=(1<<j)];
}
return i;
}
vector<int> g[N<<1];
int fp(int u){ return (u == p[u]) ? u : p[u] = fp(p[u]); }
void dfs(int u, int p){
up[u][0] = p;
if(u != p) dep[u] = dep[p] + 1;
for(int j = 1; j<LOG; ++j) up[u][j] = up[up[u][j-1]][j-1];
for(int v: g[u]) dfs(v, u);
}
int kth_ancestor(int u, int k){
for(int j = LOG-1; j>=0; --j) if(k>>j&1) u = up[u][j];
return u;
}
int sst[N][20];
int qry(int l, int r){
if(l > r) return (int)1e9;
int j = 31 - __builtin_clz(r-l+1);
return max(sst[l][j], sst[r-(1<<j)+1][j]);
}
int GetBestPosition(int n, int c, int R, int k[], int s[], int e[]){
fill(bit, bit+n+1, 0);
LOG = 32 - __builtin_clz(n<<1);
for(int i = 0; i<(n<<1); ++i){ p[i] = i; g[i].clear(); val[i] = mp(i, i); dep[i] = 0;}
int nn = n-1;
for(int i = 0; i<nn; ++i) sst[i][0] = k[i];
for(int j = 1; j<LOG; ++j){
for(int i = 0; i+(1<<j)-1<nn; ++i){
sst[i][j] = max(sst[i][j-1], sst[i+(1<<(j-1))][j-1]);
}
}
set<int> st;
int root = 0;
for(int i = 0; i<n; ++i){
st.insert(i);
inter[i] = mp(i, i);
upd(i, +1);
}
for(int i = 0; i<c; ++i){
int l = pos(s[i]+1), r = pos(e[i]+1), rt = n + i;
vector<int> tmp;
for(auto itr = st.lower_bound(l); itr != st.end() && *itr <= r; ++itr){
g[rt].push_back(fp(*itr));
val[rt] = {val[fp(l)].F , val[fp(r)].S};
p[fp(*itr)] = rt;
if(*itr > l) tmp.push_back(*itr);
}
for(int j : tmp) upd(j, -1), st.erase(j);
root = max(root, rt);
}
dfs(root, root);
int ans = 0, mx = 0;
for(int i = 0; i<n; ++i){
int low = 1, high = dep[i], cnt_win = 0;
while(low <= high){
int mid = low + ((high-low)>>1);
int anc = kth_ancestor(i, mid);
int l = val[anc].F, r = val[anc].S;
int cmp = max(qry(l, i-1), qry(i, r-1));
if(R > cmp){
low = mid+1; cnt_win = mid;
}else{
high = mid-1;
}
}
if(cnt_win > mx){
mx = cnt_win; ans = i;
}
}
return ans;
}
/*
signed main(){
int n, c, R; scanf("%d %d %d", &n, &c, &R);
int k[n], s[c], e[c];
for(int i = 0; i<n-1; ++i) scanf("%d", k+i);
for(int i = 0; i<c; ++i) scanf("%d", s+i);
for(int i = 0; i<c; ++i) scanf("%d", e+i);
printf("%d", GetBestPosition(n, c, R, k, s, e));
}
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |