Submission #1111802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111802		ThegeekKnight16	Jousting tournament (IOI12_tournament)	C++17	100 / 100	125 ms	17356 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
array<array<int, 2>, 4*MAXN> seg, lz;

void refresh(int pos, int ini, int fim, int type)
{
    if (lz[pos][type] == 1) return;
    lz[pos][type] = 1; seg[pos][type] = 0;

    if (ini == fim) return;
    int e = 2*pos, d = e+1;
    lz[e][type] = lz[d][type] = 0;
}

void refresh(int pos, int ini, int fim)
{
    refresh(pos, ini, fim, 0);
    refresh(pos, ini, fim, 1);
}

void build(int pos, int ini, int fim)
{
    if (ini == fim)
    {
        seg[pos] = lz[pos] = {1, 1};
        return;
    }
    int m = (ini + fim) >> 1;
    int e = 2*pos, d = e+1;
    build(e, ini, m);
    build(d, m+1, fim);
    seg[pos] = {seg[e][0] + seg[d][0], seg[e][1] + seg[d][1]};
    lz[pos] = {1, 1};
}

void update(int pos, int ini, int fim, int p, int q, int type)
{
    refresh(pos, ini, fim);
    if (q < ini || p > fim) return;
    if (p <= ini && fim <= q)
    {
        lz[pos][type] = 0;
        refresh(pos, ini, fim);
        return;
    }
    int m = (ini + fim) >> 1;
    int e = 2*pos, d = e+1;
    update(e, ini, m, p, q, type);
    update(d, m+1, fim, p, q, type);
    seg[pos] = {seg[e][0] + seg[d][0], seg[e][1] + seg[d][1]};
}

int bb(int pos, int ini, int fim, int val, int type)
{
    if (ini == fim) return ini;
    int m = (ini + fim) >> 1;
    int e = 2*pos, d = e+1;
    if (val <= seg[e][type]) return bb(e, ini, m, val, type);
    else return bb(d, m+1, fim, val-seg[e][type], type);
}

int GetBestPosition(int N, int C, int R, int K[], int S[], int E[])
{
    build(1, 1, N);
    for (int i = 0; i < C; i++)
    {
        S[i] = bb(1, 1, N, S[i]+1, 0); E[i] = bb(1, 1, N, E[i]+1, 1);
        update(1, 1, N, S[i]+1, E[i], 0); update(1, 1, N, S[i], E[i]-1, 1);
    }

    vector<array<int, 20>> dp(N);
    for (int i = 1; i < N; i++) dp[i][0] = K[i-1];
    for (int k = 1; k < 20; k++)
        for (int i = 1; i < N; i++)
            dp[i][k] = max(dp[i][k-1], dp[min(N-1, i+(1<<(k-1)))][k-1]);

    vector<pair<int, int>> sweep;
    for (int i = 0; i < C; i++)
    {
        int tam = E[i]-S[i];
        int k = 31 - __builtin_clz(tam);
        int val = max(dp[S[i]][k], dp[E[i]-(1<<k)][k]);
        if (val < R) sweep.emplace_back(S[i], 0), sweep.emplace_back(E[i], 1);
    }

    int resp = 0, aux = 0, respId = 1;
    sort(sweep.begin(), sweep.end());
    for (auto [x, t] : sweep)
    {
        aux += (t == 0 ? 1 : -1);
        if (aux > resp) respId = x, resp = aux;
    }

    return respId-1;
}

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