Submission #103801

#	Time	Username	Problem	Language	Result	Execution time	Memory
103801		alexpetrescu	Jousting tournament (IOI12_tournament)	C++14	100 / 100	222 ms	8728 KiB

tournament

#include <algorithm>

#define MAXN 200009
#define MAXP 265000

int aint[MAXP], t[MAXN];
int val[MAXN], v[MAXN], calc[MAXN];
int best[MAXN], l[MAXN], r[MAXN];
int N, R, rez, left, right, cnt, poz;

void dfs(int p, int st, int dr) {
    aint[p] = dr - st + 1;
    if (st < dr) {
        int m = (st + dr) / 2;
        dfs(2 * p, st, m);
        dfs(2 * p + 1, m + 1, dr);
    }
}

void update(int p, int st, int dr) {
    if (st == dr)
        aint[p] = val[st] != -1;
    else {
        int m = (st + dr) / 2;
        if (poz <= m) update(2 * p, st, m);
        else update(2 * p + 1, m + 1, dr);
        aint[p] = aint[2 * p] + aint[2 * p + 1];
    }
}

void query(int p, int st, int dr) {
    if (st == dr)
        poz = st;
    else {
        int m = (st + dr) / 2;
        if (cnt <= aint[2 * p])
            query(2 * p, st, m);
        else {
            cnt -= aint[2 * p];
            query(2 * p + 1, m + 1, dr);
        }
    }
}

void DFS(int p, int st, int dr) {
    if (st == dr)
        aint[p] = v[st];
    else {
        int m = (st + dr) / 2;
        DFS(2 * p, st, m);
        DFS(2 * p + 1, m + 1, dr);
        aint[p] = std::max(aint[2 * p], aint[2 * p + 1]);
    }
}

void UPDATE(int p, int st, int dr) {
    if (st == dr)
        aint[p] = v[st];
    else {
        int m = (st + dr) / 2;
        if (left <= m) UPDATE(2 * p, st, m);
        if (m < right) UPDATE(2 * p + 1, m + 1, dr);
        aint[p] = std::max(aint[2 * p], aint[2 * p + 1]);
    }
}

void QUERY(int p, int st, int dr) {
    if (left <= st && dr <= right)
        rez = std::max(rez, aint[p]);
    else {
        int m = (st + dr) / 2;
        if (left <= m) QUERY(2 * p, st, m);
        if (m < right) QUERY(2 * p + 1, m + 1, dr);
    }
}

void solve(int x) {
    rez = -1;
    left = l[x];
    right = r[x];
    QUERY(1, 0, N - 1);

    if (best[x] == rez)
        return ;

    best[x] = rez;
    if (t[x] != -1)
        solve(t[x]);

    if (best[x] == R) {
        calc[x] = 1;
        if (t[x] != -1)
            calc[x] += calc[t[x]];
    } else
        calc[x] = 0;
}

int GetBestPosition(int ceecunumarulasta, int C, int darcuastalalaltcei, int *K, int *S, int *E) {
    N = ceecunumarulasta;
    R = darcuastalalaltcei;
    for (int i = 0; i < N; i++)
        val[i] = i, l[i] = i, r[i] = i;
    dfs(1, 0, N - 1);

    for (int i = 0; i < N + C; i++)
        t[i] = -1;
    for (int i = 0; i < C; i++) {
        cnt = S[i] + 1;
        query(1, 0, N - 1);
        int pos = poz;
        l[i + N] = l[val[poz]];
        t[val[poz]] = i + N;
        val[poz] = -1;
        update(1, 0, N - 1);
        int u = E[i] - S[i];
        while (u > 0) {
            u--;
            cnt = S[i] + 1;
            query(1, 0, N - 1);
            t[val[poz]] = i + N;
            r[i + N] = r[val[poz]];
            val[poz] = -1;
            update(1, 0, N - 1);
        }
        poz = pos;
        val[poz] = i + N;
        update(1, 0, N - 1);
    }

    for (int i = 0; i < N - 1; i++)
        v[i] = K[i];
    v[N - 1] = R;
    DFS(1, 0, N - 1);

    for (int i = C + N - 1; i >= 0; i--) {
        rez = -1;
        left = l[i];
        right = r[i];
        QUERY(1, 0, N - 1);
        best[i] = rez;

        if (best[i] == R) {
            calc[i] = 1;
            if (t[i] != -1)
                calc[i] += calc[t[i]];
        }
    }

    int ans = calc[N - 1], sol = N - 1;
    for (int i = N - 2; i >= 0; i--) {
        v[i + 1] = v[i];
        v[i] = R;
        left = i;
        right = i + 1;
        UPDATE(1, 0, N - 1);

        solve(i + 1);
        solve(i);
        if (calc[i] >= ans)
            ans = calc[i], sol = i;
    }

    return sol;
}

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