oj.uz

Submission #258801

# Submission time Handle Problem Language Result Execution time Memory
258801 2020-08-06T14:59:23 Z SamAnd Jousting tournament (IOI12_tournament) C++17
100 / 100
 166 ms 21884 KB 
#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.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 6 ms 1408 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 7 ms 1408 KB Output is correct
5 Correct 6 ms 1280 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct
7 Correct 7 ms 1408 KB Output is correct
8 Correct 6 ms 1408 KB Output is correct
9 Correct 4 ms 1024 KB Output is correct
10 Correct 7 ms 1408 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 9336 KB Output is correct
2 Correct 133 ms 21820 KB Output is correct
3 Correct 80 ms 12560 KB Output is correct
4 Correct 152 ms 21880 KB Output is correct
5 Correct 124 ms 21112 KB Output is correct
6 Correct 166 ms 18296 KB Output is correct
7 Correct 129 ms 21880 KB Output is correct
8 Correct 136 ms 21884 KB Output is correct
9 Correct 66 ms 11824 KB Output is correct
10 Correct 75 ms 12280 KB Output is correct