Submission #483599

#	Time	Username	Problem	Language	Result	Execution time	Memory
483599		blue	Jousting tournament (IOI12_tournament)	C++17	100 / 100	171 ms	31144 KiB

tournament

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

/*
N knights
C rounds S[i] - E[i]
R-ranked late knight
K = initial ordering of present knights.

N+C no
*/

int N;

const int maxN = 100'000;
const int logN = 18;

vector<int> BIT(1+maxN, 0);

vector<int> lft(2*maxN);
vector<int> rgt(2*maxN);
vector<int> nxt(maxN), prv(maxN);
vector<int> parent(2*maxN);

vector< vector<int> > anc(2*maxN+1, vector<int>(1+logN, -1));
vector<int> depth(2*maxN+1);

void add(int I, int V)
{
    for(int j = I+1; j <= N; j += j&-j)
        BIT[j] += V;
}

int prefsum(int I)
{
    int res = 0;
    for(int j = I+1; j >= 1; j -= j&-j)
        res += BIT[j];
    return res;
}

void disable(int p)
{
    if(0 <= prv[p])
        nxt[ prv[p] ] = nxt[p];

    if(nxt[p] <= N-1)
        prv[ nxt[p] ] = prv[p];

    add(p, -1);
}

int lca(int u, int v)
{
    if(depth[u] > depth[v]) swap(u, v);
    for(int e = logN; e >= 0; e--)
    {
        if(depth[anc[v][e]] < depth[u])
            continue;

        v = anc[v][e];
    }

    if(u == v) return u;

    for(int e = logN; e >= 0; e--)
    {
        if(anc[v][e] == anc[u][e])
            continue;

        v = anc[v][e];
        u = anc[u][e];
    }

    return anc[u][0];
}


int GetBestPosition(int N_, int C, int R, int *K, int *S, int *E)
{
    N = N_;

    for(int i = 0; i < N; i++)
    {
        nxt[i] = i+1;
        prv[i] = i-1;
    }

    for(int i = 1; i < N; i++)
        add(i, +1);

    // cerr << "resultant array: ";
    // for(int i = 0; i < N; i++) cerr << prefsum(i) << ' ';
    // cerr << '\n';


    for(int i = 0; i < N; i++)
    {
        lft[i] = rgt[i] = i;
    }

    for(int c = 0; c < C; c++)
    {
        // cerr << "\n\n\n";
        // cerr << "op: " << S[c] << ' ' << E[c] << '\n';
        int lo = 0;
        int hi = N-1;
        while(lo != hi)
        {
            int mid = (lo+hi)/2;
            if(prefsum(mid) < S[c])
                lo = mid+1;
            else
                hi = mid;
        }
        int p = lo;

        lft[N+c] = p;

        for(int r = 1; r <= E[c] - S[c]; r++)
        {
            p = nxt[p];
            disable(p);
            // cerr << "disable " << p << '\n';
            //
            // cerr << "resultant array: ";
            // for(int i = 0; i < N; i++) cerr << prefsum(i) << ' ';
            // cerr << '\n';
        }
        rgt[N+c] = nxt[p] - 1;


        // cerr << c << ": " << lft[c] << ' ' << rgt[c] << '\n';
    }

    vector<int> I(N+C);
    for(int i = 0; i < N+C; i++) I[i] = i;
    sort(I.begin(), I.end(), [] (int p, int q)
    {
        if(lft[p] != lft[q]) return lft[p] < lft[q];
        else return p > q;
    });

    vector<int> st;
    st.push_back(I[0]);

    parent[I[0]] = N+C;
    anc[I[0]][0] = N+C;
    anc[N+C][0] = N+C;
    depth[N+C] = -1;

    for(int j = 1; j < N+C; j++)
    {
        int i = I[j];
        while(!(lft[st.back()] <= lft[i] && rgt[i] <= rgt[st.back()]))
            st.pop_back();

        parent[i] = st.back();
        anc[i][0] = st.back();
        // cerr << "parent " << lft[i] << ' ' << rgt[i] << " = " << lft[parent[i]] << ' ' << rgt[parent[i]] << '\n';

        st.push_back(i);
    }

    for(int i = N+C-1; i >= 0; i--) depth[i] = 1 + depth[parent[i]];

    // cerr << "check\n";
    for(int e = 1; e <= 18; e++)
    {
        for(int i = 0; i <= N+C; i++)
        {
            // cerr << e << ' ' << i << '\n';
            anc[i][e] = anc[ anc[i][e-1] ][e-1];
        }
    }

    vector<int> left_recent(N, -1), right_recent(N, -1); //most recent element > R

    if(K[0] > R)
        left_recent[0] = 0;

    // cerr << "??? " << K[0] << ' ' << R << '\n';

    // cerr << left_recent[0] << '\n';
    for(int i = 1; i < N-1; i++)
    {
        left_recent[i] = left_recent[i-1];
        if(K[i] > R)
            left_recent[i] = i;
    }

    if(K[N-2] > R)
        right_recent[N-2] = N-2;

    for(int i = N-3; i >= 0; i--)
    {
        right_recent[i] = right_recent[i+1];
        if(K[i] > R)
            right_recent[i] = i;
    }

    int curr_ans;
    int best_pos = 0;

    if(right_recent[0] == -1)
        curr_ans = depth[0];
    else
        curr_ans = depth[0] - depth[lca(0, right_recent[0]+1)] - 1;


// cerr << "!!!\n";
    // cerr << right_recent[0] << ' ' << lca(0, right_recent[0]+1) << '\n';

// cerr << "\n\n\n\n";
    // cerr << "0: ans = " << curr_ans << '\n';

    for(int i = 1; i < N; i++)
    {
        int this_res = depth[i];

        if(left_recent[i-1] != -1)
            this_res = min(this_res, depth[i] - depth[lca(i, left_recent[i-1])] - 1);

        if(i <= N-2)
            if(right_recent[i] != -1)
                this_res = min(this_res, depth[i] - depth[lca(i, right_recent[i]+1)] - 1);

        // cerr << left_recent[i-1] << ' ' << right_recent[i]+1 << '\n';

        // cerr << "i = " << i << ": " << left_recent[i-1] << '\n';

        if(this_res > curr_ans)
        {
            curr_ans = this_res;
            best_pos = i;
        }

        // cerr << i << ": ans = " << this_res << '\n';
    }

    // cerr << lft[3] << ' ' << rgt[3] << ' ' << parent[3] << ' ' << parent[parent[3]] << '\n';
    // cerr << parent[4] << ' ' << parent[parent[4]] << '\n';
    //
    // cerr << depth[4] << '\n';
    // cerr << left_recent[3] << '\n';
    // cerr << lca(4, left_recent[3]) << '\n';

    return best_pos;
}

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