oj.uz

Submission #256403

# Submission time Handle Problem Language Result Execution time Memory
256403 2020-08-02T16:13:49 Z Akashi Jousting tournament (IOI12_tournament) C++14
100 / 100
 195 ms 40824 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 5 ms 5120 KB Output is correct
6 Correct 5 ms 5248 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Correct 4 ms 5120 KB Output is correct
10 Correct 5 ms 5120 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5248 KB Output is correct
2 Correct 11 ms 6784 KB Output is correct
3 Correct 9 ms 6144 KB Output is correct
4 Correct 10 ms 6656 KB Output is correct
5 Correct 11 ms 6656 KB Output is correct
6 Correct 11 ms 6400 KB Output is correct
7 Correct 13 ms 6784 KB Output is correct
8 Correct 16 ms 6656 KB Output is correct
9 Correct 7 ms 6016 KB Output is correct
10 Correct 11 ms 6656 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 18680 KB Output is correct
2 Correct 195 ms 40824 KB Output is correct
3 Correct 113 ms 25204 KB Output is correct
4 Correct 187 ms 38264 KB Output is correct
5 Correct 191 ms 38264 KB Output is correct
6 Correct 179 ms 32208 KB Output is correct
7 Correct 192 ms 39160 KB Output is correct
8 Correct 185 ms 39160 KB Output is correct
9 Correct 104 ms 24304 KB Output is correct
10 Correct 113 ms 25080 KB Output is correct