Submission #256403

#	Time	Username	Problem	Language	Result	Execution time	Memory
256403		Akashi	Jousting tournament (IOI12_tournament)	C++14	100 / 100	195 ms	40824 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

const int DIM = 1e5 + 5;

int n, nr;
int h[2 * DIM];
int tt[2 * DIM][20], mx[DIM][20];
vector <int> v[2 * DIM];

int sum[4 * DIM], arb[4 * DIM];

void build(int st = 0, int dr = n - 1, int nod = 1) {
    if (st == dr) {arb[nod] = st; sum[nod] = 1; return ;}

    int mij = (st + dr) / 2;
    build(st, mij, nod * 2);
    build(mij + 1, dr, nod * 2 + 1);

    sum[nod] = sum[nod * 2] + sum[nod * 2 + 1];
}

void update(int pos, int x, int y, int st = 0, int dr = n - 1, int nod = 1) {
    if (st == dr) {arb[nod] = x; sum[nod] = y; return ;}

    int mij = (st + dr) / 2;
    if (pos <= mij) update(pos, x, y, st, mij, nod * 2);
    else update(pos, x, y, mij + 1, dr, nod * 2 + 1);

    sum[nod] = sum[nod * 2] + sum[nod * 2 + 1];
}

pair <int, int> find(int pos, int st = 0, int dr = n - 1, int nod = 1) {
    if (st == dr) return {arb[nod], st};

    int mij = (st + dr) / 2;
    if (pos <= sum[nod * 2]) return find(pos, st, mij, nod * 2);
    return find(pos - sum[nod * 2], mij + 1, dr, nod * 2 + 1);
}

void dfs(int nod) {
    for (auto it : v[nod]) {
        h[it] = h[nod] + 1;
        tt[it][0] = nod;
        dfs(it);
    }
}

int find_left(int pos, int val) {
    for (int k = 19; k >= 0 ; --k) {
        if (pos - (1 << k) + 1 < 0) continue ;
        if (mx[pos - (1 << k) + 1][k] <= val) pos -= (1 << k);
    }

    return pos;
}

int find_right(int pos, int val) {
    for (int k = 19; k >= 0 ; --k) {
        if (pos + (1 << k) - 1 >= n - 1) continue ;
        if (mx[pos][k] <= val) pos += (1 << k);
    }

    return pos;
}

int get_lca(int x, int y, bool wh) {
    if (h[x] < h[y]) swap(x, y), wh = 1 - wh;
    int ans = 0;
    if (wh) ans = h[x] - h[y];

    int dif = h[x] - h[y], k = 19;
    while (dif > 0) {
        if (dif & (1 << k)) {
            dif = dif ^ (1 << k);
            x = tt[x][k];
        }
        --k;
    }

    if (x == y) return ans;

    for (int k = 19; k >= 0 ; --k) {
        if (tt[x][k] != tt[y][k]) {
            x = tt[x][k]; y = tt[y][k];
            ans = ans + (1 << k);
        }
    }

    return ans + 1;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n = N;
    nr = n - 1;
    build();

    for (int i = 0; i < C ; ++i) {
        ++nr;

        for (int j = E[i]; j >= S[i] ; --j) {
            pair <int, int> x = find(j + 1);
            v[nr].push_back(x.first);

            if (j > S[i]) update(x.second, 0, 0);
            else update(x.second, nr, 1);
        }
    }

    dfs(nr);

    for (int i = 0; i < n - 1 ; ++i) mx[i][0] = K[i];

    for (int k = 1; k <= 19 ; ++k) {
        for (int i = 0; i < nr ; ++i)
            tt[i][k] = tt[tt[i][k - 1]][k - 1];

        for (int i = 0; i < n - 1 ; ++i) {
            if (i + (1 << (k - 1)) - 1 < n - 1)
                mx[i][k] = max(mx[i][k - 1], mx[i + (1 << (k - 1))][k - 1]);
            else
                mx[i][k] = mx[i][k - 1];

        }
    }

    int sol = 0, pos = -1;
    for (int i = 0; i < n ; ++i) {

        int l = find_left(i - 1, R);
        int r = find_right(i, R);
        ++r;

        int ans = get_lca(nr, i, 0);
        if (l >= 0) ans = min(ans, get_lca(l, i, 0));
        if (r < n) ans = min(ans, get_lca(r, i, 0));

        if (ans > sol) sol = ans, pos = i;
    }

    return pos;
}
/**
5 3 3
1
0
2
4
1 3
0 1
0 1


**/

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