Submission #256366

#	Time	Username	Problem	Language	Result	Execution time	Memory
256366		Akashi	Jousting tournament (IOI12_tournament)	C++14	0 / 100	1080 ms	16652 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;
        cerr << nod << " " << it << endl;
        dfs(it);
    }
}

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

    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);
            update(x.second, 0, -1);
        }

        update(S[i], 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)) < 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;
    for (int i = 0; i < n ; ++i) {
        int l = find_left(i, R);
        if (K[l] <= R) --l;
        int r = find_right(i, R);
        if (K[r] <= R) ++r;
        ++r;

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

        sol = max(sol, ans);
    }

    return sol - 1;
}
/**
5 3 3
1
0
2
4
1 3
0 1
0 1

**/

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