#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 10;
struct vv{
int mn, mx;
vector<int> child;
};
vector<vv> g(2*N);
int dep[2*N], k[N], seg[8*N], r, n, c, fen[N], idx[N], ans, ans2 = 1e9;
pii mxdep[2*N];
void update( int x ) { for( int i = x ; i <= N ; i += ( i & -i ) ) fen[i] -= 1; }
int query( int x ) {
int ret = 0;
for( int i = x ; i > 0 ; i -= ( i & -i ) ) ret += fen[i];
return ret;
}
int get( int x ) {
int l = 1, r = n;
while( l < r ) {
int m = ( l + r ) >> 1;
//printf("%d %d %d\n",l,r,query(m));
if( query( m ) >= x ) r = m;
else l = m + 1;
}
return r;
}
void build( int l = 1, int r = n-1, int now = 1 ) {
if( l == r ) return void( seg[now] = k[l] );
int mid = ( l + r ) >> 1;
build( l, mid, now << 1 ), build( mid + 1, r, now << 1 | 1 );
seg[now] = max( seg[now<<1], seg[now<<1|1] );
return ;
}
int getmx( int ll, int rr, int l = 1, int r = n-1, int now = 1 ) {
if( l > rr || r < ll ) return -1;
if( l >= ll && r <= rr ) return seg[now];
int mid = ( l + r ) >> 1;
return max( getmx( ll, rr, l, mid, now << 1 ), getmx( ll, rr, mid + 1, r, now << 1 | 1 ) );
}
pii dfs( int now, int p, int de ) {
dep[now] = de;
mxdep[now] = pii( de, now );
for( int i : g[now].child ) if( i != p ) {
pii z = dfs( i, now, de + 1 );
if( z.x > mxdep[now].x ) mxdep[now] = z;
else if( z.x == mxdep[now].x && z.y < mxdep[now].y ) mxdep[now] = z;
}
return mxdep[now];
}
void dfs2( int now, int p ) {
int mx = getmx( g[now].mn, g[now].mx - 1 );
if( mx <= r ) {
if( ans < mxdep[now].x-dep[now]+1 ) ans2 = mxdep[now].y;
else if( ans == mxdep[now].x-dep[now]+1 ) ans2 = min( ans2, mxdep[now].y );
ans = max( ans, mxdep[now].x-dep[now]+1 );
}
//printf("%d %d %d %d\n",mx,now,g[now].mn,g[now].mx);
for( int i : g[now].child ) if( i != p ) dfs2( i, now );
}
int GetBestPosition(int NN, int C, int R, int K[], int S[], int E[] ) {
n = NN, r = R, c = C;
for( int i = 1 ; i <= n ; i++ ) for( int j = i ; j <= n ; j += ( j & -j ) ) fen[j] += 1;
for( int i = 1 ; i <= n - 1 ; i++ ) k[i] = K[i-1];
for( int i = 1 ; i <= n ; i++ ) idx[i] = i, g[i].mx = i, g[i].mn = i;
for( int i = N+1 ; i < 2*N ; i++ ) g[i].mx = -1, g[i].mn = i;
for( int i = 1 ; i <= c ; i++ ) {
int s = S[i-1] + 1, e = E[i-1] + 1;
vector<int> vec;
for( int j = s ; j <= e ; j++ ) {
vec.emplace_back( get( j ) );
//printf("%d %d\n",j,get(j));
}
// printf("%d\n",i+N);
for( int v : vec ){
//printf("%d ",v);
g[i+N].child.emplace_back( idx[v] );
if( v != vec[0] ) update( v );
g[i+N].mx = max( g[i+N].mx, g[idx[v]].mx ), g[i+N].mn = min( g[i+N].mn, g[idx[v]].mn );
}
//printf("\n");
idx[vec[0]] = i + N;
}
// for( int i = N + 1 ; i <= N + c ; i++ ) {
// printf("I : %d %d %d\n",i,g[i].mx,g[i].mn);
// for( int j : g[i].child ) printf("%d ",j);
// printf("\n");
// }
build(), dfs( N+c, -1, 1 ), dfs2( N+c, -1 );
return ans2;
}
// int main()
// {
// int n, c, r, k[100], s[100], e[100];
// scanf("%d %d %d",&n,&c,&r);
// 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 ));
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
6648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
10728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
