Submission #258801

#	Time	Username	Problem	Language	Result	Execution time	Memory
258801		SamAnd	Jousting tournament (IOI12_tournament)	C++17	100 / 100	166 ms	21884 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 200005;

int n;

int t[N * 4];
int u[N];
void ubd(int tl, int tr, int x, int y, int pos)
{
    if (tl == tr)
    {
        t[pos] += y;
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, pos * 2);
    else
        ubd(m + 1, tr, x, y, pos * 2 + 1);
    t[pos] = t[pos * 2] + t[pos * 2 + 1];
}

int q;
int qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return -1;
    int m = (tl + tr) / 2;
    if (tl == l && tr == r)
    {
        if (t[pos] < q)
        {
            q -= t[pos];
            return -1;
        }
        if (tl == tr)
            return tl;
    }
    int u = qry(tl, m, l, min(m, r), pos * 2);
    if (u != -1)
        return u;
    return qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1);
}

int m;
const int k = 20;
int p[N][k];
int ul[N], ur[N];

int pr[N];

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
    n = N;

    for (int i = 0; i < n; ++i)
    {
        u[i] = i;
        ubd(0, n - 1, i, 1, 1);
        ul[i] = i;
        ur[i] = i;
    }
    m = n;
    for (int ii = 0; ii < C; ++ii)
    {
        vector<int> v;
        int l = S[ii];
        int r = E[ii];

        q = l + 1;
        v.push_back(qry(0, n - 1, 0, n - 1, 1));
        for (int i = 0; i < r - l; ++i)
        {
            q = 1;
            v.push_back(qry(0, n - 1, v.back() + 1, n - 1, 1));
        }

        ul[m] = ul[u[v[0]]];
        ur[m] = ur[u[v.back()]];
        for (int i = 0; i < sz(v); ++i)
        {
            p[u[v[i]]][0] = m;
        }

        u[v[0]] = m;
        for (int i = 1; i < sz(v); ++i)
        {
            ubd(0, n - 1, v[i], -1, 1);
        }

        m++;
    }
    p[m - 1][0] = m - 1;

    for (int x = m - 1; x >= 0; --x)
    {
        for (int i = 1; i < k; ++i)
        {
            p[x][i] = p[p[x][i - 1]][i - 1];
        }
    }

    if (R == n - 1)
    {
        return 0;
    }
    for (int i = 0; i < n - 1; ++i)
    {
        if (i)
            pr[i] = pr[i - 1];
        if (K[i] > R)
            pr[i]++;
    }

    int anss = -1;
    int ans = -1;
    for (int s = 0; s < n; ++s)
    {
        int x = s;
        int yans = 0;
        for (int i = k - 1; i >= 0; --i)
        {
            int l = ul[p[x][i]];
            int r = ur[p[x][i]];
            --r;
            int s = pr[r];
            if (l)
                s -= pr[l - 1];
            if (!s)
            {
                yans += (1 << i);
                x = p[x][i];
            }
        }
        if (yans > ans)
        {
            ans = yans;
            anss = s;
        }
    }
    return anss;
}

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