Submission #1035080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035080		12345678	Jousting tournament (IOI12_tournament)	C++17	100 / 100	327 ms	34132 KiB

tournament

#include <bits/stdc++.h>
 
using namespace std;
 
const int nx=1e5+5, kx=18;
 
int n, c[2*nx], rt, nd[nx], cur, pa[2*nx][kx], lvl[2*nx], in[2*nx], out[2*nx], t, res;
vector<int> d[2*nx];
 
void dfs(int u, int p)
{
    in[u]=++t;
    lvl[u]=lvl[p]+1;
    pa[u][0]=p;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto v:d[u]) dfs(v, u);
    out[u]=t;
    //cout<<"tour "<<u<<' '<<in[u]<<' '<<out[u]<<'\n';
}
 
struct segtree
{
    int d[8*nx];
    void build(int l, int r, int i)
    {
        d[i]=0;
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
    }
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]+=vl, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql ,qr)+query(md+1, r, 2*i+1, ql, qr);
    }
    int query2(int l, int r, int i, int key)
    {
        if (l==r) return l;
        int md=(l+r)/2;
        if (d[2*i]>=key) return query2(l, md, 2*i, key);
        else return query2(md+1, r, 2*i+1, key-d[2*i]);
    }
} s;
 
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n=cur=N;
    for (int i=1; i<=N; i++) nd[i]=i, s.update(1, N, 1, i, 1);
    for (int i=0; i<C; i++)
    {
        cur++;
        for (int j=S[i]+1; j<=E[i]+1; j++)
        {
            int idx=s.query2(1, N, 1, S[i]+1);
            d[cur].push_back(nd[idx]);
            if (j==E[i]+1) nd[idx]=cur;
            else s.update(1, N, 1, idx, -1);
        }
    }
    s.build(1, 2*N, 1);
    for (int i=2; i<=N; i++) c[i]=K[i-2]>R;
    rt=cur;
    dfs(rt, rt);
    for (int i=1; i<=N; i++) s.update(1, 2*N, 1, in[i], c[i]); //cout<<"update "<<i<<' '<<in[i]<<' '<<c[i]<<'\n';
    pair<int, int> mx={-1, -1};
    if (R==N-1)
    {
        for (int i=1; i<=N; i++) mx=max(mx, {lvl[i]-1, -i});
        return cout<<-mx.second-1, 0;
    }
    for (int i=1; i<=N; i++)
    {
        if (i!=1) 
        {
            s.update(1, 2*N, 1, in[i-1], -c[i-1]);
            s.update(1, 2*N, 1, in[i], -c[i]);
            swap(c[i], c[i-1]);
            s.update(1, 2*N, 1, in[i-1], c[i-1]);
            s.update(1, 2*N, 1, in[i], c[i]);
        }
        int u=i;
        for (int j=kx-1; j>=0; j--) if (s.query(1, 2*N, 1, in[pa[u][j]], out[pa[u][j]])==0) u=pa[u][j];
        mx=max(mx, {lvl[i]-lvl[u], -i});
    }
    return -mx.second-1;
}

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