oj.uz

Submission #1035225

# Submission time Handle Problem Language Result Execution time Memory
1035225 2024-07-26T07:03:56 Z sleepntsheep Jousting tournament (IOI12_tournament) C
100 / 100
 141 ms 8532 KB 
#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 qq(int l, int r) {
    int z=-1;for(l+=NN,r+=NN+1;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 *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 = ft_upperbound(E[i]) - 1;
        if (r >= N)
            r = N - 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 lb = -1, ub = C;
        while (ub - lb > 1) {
            int md = lb + (ub - lb) / 2;
            if (qq(0, md) <= R)lb=md;
            else ub=md;
        }

        int x = search(1, 0, NN - 1, R);

        if (ft_sum(x) > z)
            z = ft_sum(x), best = i;
    }



    return best;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 6 ms 3260 KB Output is correct
3 Correct 3 ms 2908 KB Output is correct
4 Correct 6 ms 3164 KB Output is correct
5 Correct 9 ms 3008 KB Output is correct
6 Correct 5 ms 3416 KB Output is correct
7 Correct 10 ms 3164 KB Output is correct
8 Correct 6 ms 3160 KB Output is correct
9 Correct 2 ms 2904 KB Output is correct
10 Correct 7 ms 3164 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 4948 KB Output is correct
2 Correct 141 ms 8532 KB Output is correct
3 Correct 60 ms 3928 KB Output is correct
4 Correct 131 ms 8464 KB Output is correct
5 Correct 124 ms 8272 KB Output is correct
6 Correct 98 ms 6992 KB Output is correct
7 Correct 134 ms 8524 KB Output is correct
8 Correct 129 ms 8528 KB Output is correct
9 Correct 22 ms 3676 KB Output is correct
10 Correct 49 ms 4956 KB Output is correct