Submission #169447

#	Time	Username	Problem	Language	Result	Execution time	Memory
169447		arnold518	Jousting tournament (IOI12_tournament)	C++14	100 / 100	375 ms	34260 KiB

tournament

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, C, R, K[MAXN+10], S[MAXN+10], E[MAXN+10];

struct BIT
{
    int bit[MAXN+10];
    void update(int i, int v) { for(; i<=N; i+=(i&-i)) bit[i]+=v; }
    int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=bit[i]; return ret; }
    int getpos(int x)
    {
        int lo=0, hi=N;
        while(lo+1<hi)
        {
            int mid=lo+hi>>1;
            if(query(mid)>=x) hi=mid;
            else lo=mid;
        }
        return hi;
    }
}bitl, bitr;

vector<int> adj[MAXN*2+10];
int dep[MAXN*2+10], par[MAXN*2+10][25], dp[MAXN*2+10];
int ans1, ans2;

int lca(int u, int v)
{
    int i, j;
    if(dep[u]>dep[v]) swap(u, v);
    for(i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u]) v=par[v][i];
    if(u==v) return v;
    for(i=20; i>=0; i--) if(par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i];
    return par[u][0];
}

int GetBestPosition(int _N, int _C, int _R, int *_K, int *_S, int *_E)
{
    int i, j;
    N=_N; C=_C; R=_R;

    R++;
    for(i=1; i<N; i++)  K[i]=_K[i-1]+1;
    for(i=1; i<=C; i++) S[i]=_S[i-1]+1;
    for(i=1; i<=C; i++) E[i]=_E[i-1]+1;

    for(i=1; i<=N; i++) bitl.update(i, 1), bitr.update(i, 1);
    for(i=1; i<=C; i++)
    {
        int s=bitl.getpos(S[i]), e=bitr.getpos(E[i]);
        vector<int> DL, DR;
        for(j=S[i]; j<=E[i]; j++) DL.push_back(bitl.getpos(j)), DR.push_back(bitr.getpos(j));
        for(auto it : DL) bitl.update(it, -1);
        for(auto it : DR) bitr.update(it, -1);
        bitl.update(s, 1);
        bitr.update(e, 1);
        S[i]=s; E[i]=e;
    }

    map<int, int> M;
    for(i=1; i<=N; i++) M[i]=i;
    for(i=1; i<=C; i++)
    {
        auto st=M.lower_bound(S[i]), et=M.upper_bound(E[i]);
        vector<map<int, int>::iterator> V;
        for(auto it=st; it!=et; it++)
        {
            V.push_back(it);
            adj[i+N].push_back(it->second);
            par[it->second][0]=i+N;
        }
        for(auto it : V) M.erase(it);
        M[S[i]]=i+N;
    }

    dep[C+N]=1;
    for(i=C; i>=1; i--)
    {
        int now=i+N;
        for(auto nxt : adj[now]) dep[nxt]=dep[now]+1;
    }

    for(i=1; i<=20; i++) for(j=1; j<=N+C; j++) par[j][i]=par[par[j][i-1]][i-1];

    lca(1, 3);

    vector<int> pos;
    for(i=1; i<N; i++) if(K[i]>R) pos.push_back(i);

    for(i=1; i<=N; i++)
    {
        int now=1;
        auto it=lower_bound(pos.begin(), pos.end(), i);
        if(it!=pos.begin())
        {
            auto jt=it; jt--;
            int w=lca(*jt, i);
            //printf("!%d %d -> %d\n", *jt, i, w);
            now=max(now, dep[w]);
        }
        if(it!=pos.end())
        {
            auto jt=it;
            int w=lca(*jt+1, i);
            //printf("!%d %d -> %d\n", *jt+1, i, w);
            now=max(now, dep[w]);
        }

        now=dep[i]-now-1;
        //printf("%d : %d\n", i, now);
        if(now!=987654320 && ans1<now) ans1=now, ans2=i-1;
    }
    return ans2;
}

Compilation message (stderr)

tournament.cpp: In member function 'int BIT::getpos(int)':
tournament.cpp:25:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid=lo+hi>>1;
                     ~~^~~
tournament.cpp: In function 'int lca(int, int)':
tournament.cpp:39:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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