Submission #1035228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035228		sleepntsheep	Jousting tournament (IOI12_tournament)	C11	100 / 100	96 ms	8528 KiB

tournament

#include<stdlib.h>
#include<stdio.h>
#define NN (1<<17)
int min(int i, int j) {
    return i < j ? i : j;
}
int max(int i, int j) {
    return i > j ? i : j;
}

int ft[NN];
void ft_add(int p, int k) {
    for (; p < NN; p |= p + 1)
        ft[p] += k;
}
int ft_sum(int p) {
    int z = 0;
    for (; p > 0; p &= p - 1)
        z += ft[p - 1];
    return z;
}
int ft_upperbound(int k) {
    int sum = 0, pos = 0;
    for (int j = 1 << 20; j >= 1; j /= 2)
        if (pos + j <= NN && sum + ft[pos + j - 1] <= k)
            sum += ft[(pos += j) - 1];
    return pos;
}

int st[NN * 2];
int rmq(int l, int r) {
    int z = -1;
    for (l += NN, r += NN; l < r; l /= 2, r /= 2) {
        if (l & 1) z = max(z, st[l++]);
        if (r & 1) z = max(st[--r], z);
    }
    return z;
}

int st_[NN * 2];
void update(int p, int k) {
    for (st_[p += NN] = k; p /= 2; )
        st_[p] = max(st_[p * 2], st_[p * 2 + 1]);
}

int search(int ii, int l, int r, int k) {
    if (l == r)
        return st_[ii] <= k ? l + 1 : l;
    if (st_[ii * 2] <= k)
        return search(ii * 2 + 1, l + (r - l) / 2 + 1, r, k);
    return search(ii * 2, l, l + (r - l) / 2, k);
}

int *eh[NN], eo[NN];

void pus(int i, int j) {
    int o = eo[i]++;
    if (!o) eh[i] = (int*)malloc(2 * sizeof **eh);
    else if (!(o & (o - 1))) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
    eh[i][o] = j;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    for (int i = 0; i < N; ++i)
        ft_add(i, 1);

    for (int i = 0; i + 1 < N; ++i)
        st[i + NN] = K[i];
    for (int i = NN; --i;)
        st[i] = max(st[i * 2], st[i * 2 + 1]);

    for (int i = 0; i < C; ++i) {
        ++S[i];++E[i];
        int l = ft_upperbound(S[i] - 1);
        int r = min(N - 1, ft_upperbound(E[i]) - 1);
        int x = ft_sum(l), y;
        while ((y = ft_upperbound(x)) <= r)
            ft_add(y, -(ft_sum(y+1) - ft_sum(y)));
        ft_add(l, 1);
        S[i] = l;
        E[i] = r;

        pus(S[i], i + 1);
        pus(E[i] + 1, -i - 1);
    }

    for (int i = 0; i < NN; ++i)
        ft[i] = 0;

    int z = -1, best = 0;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < eo[i]; ++j) {
            int x = eh[i][j];
            if (x > 0) {
                --x;
                update(x, rmq(S[x], E[x]));
                ft_add(x, 1);
            } else {
                x = -x - 1;
                update(x, 0);
                ft_add(x, -1);
            }
        }

        int x = search(1, 0, NN - 1, R);
        if (ft_sum(x) > z)
            z = ft_sum(x), best = i;
    }

    return best;
}

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