Submission #141346

#	Time	Username	Problem	Language	Result	Execution time	Memory
141346		DodgeBallMan	Jousting tournament (IOI12_tournament)	C++14	0 / 100	81 ms	10728 KiB

tournament

#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;
// }

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51