Submission #767955

#	Time	Username	Problem	Language	Result	Execution time	Memory
767955		boris_mihov	Jousting tournament (IOI12_tournament)	C++17	100 / 100	232 ms	13524 KiB

tournament

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXLOG = 17;

int n, q;
int rank;
int a[MAXN];
int l[MAXN];
int r[MAXN];
int par[MAXN];
int first[MAXN];
int leftFrom[MAXN];
struct BIT
{
    int tree[MAXN];
    void update(int idx, int val)
    {
        for (int pos = idx ; pos <= n ; pos += pos & (-pos))
        {
            tree[pos] += val;
        }
    }

    int findKth(int k)
    {
        int pos = 0;
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (pos + (1 << log) <= n && tree[pos + (1 << log)] < k)
            {
                pos += (1 << log);
                k -= tree[pos];
            }
        }

        return pos + 1;
    }
};

struct SegmentTree
{
    int tree[4*MAXN];
    int vals[MAXN];

    int cmp(int x, int y)
    {
        if (vals[x] > vals[y]) return x;
        return y;
    }

    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node] = l;
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node);
        build(mid + 1, r, 2*node + 1);
        tree[node] = cmp(tree[2*node], tree[2*node + 1]);
    }

    void update(int l, int r, int node, int queryPos, int queryVal)
    {
        if (l == r)
        {
            vals[l] = queryVal;
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
        else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
        tree[node] = cmp(tree[2*node], tree[2*node + 1]);
    }

    int query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        int res = 0;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = cmp(res, query(l, mid, 2*node, queryL, queryR));
        if (mid + 1 <= queryR) res = cmp(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
        return res;
    }

    void build()
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            vals[i] = a[i];
        }

        build(1, n, 1);
    }

    void update(int pos, int val)
    {
        update(1, n, 1, pos, val);
    }

    int findMAX(int l, int r)
    {
        return vals[query(1, n, 1, l, r)];
    }
};

BIT fenwick;
SegmentTree tree;
struct SparseLift
{
    int sparse[MAXLOG][MAXN];
    void build(int vals[])
    {
        for (int i = 1 ; i <= q ; ++i)
        {
            sparse[0][i] = vals[i];
        }

        for (int log = 1 ; (1 << log) <= q ; ++log)
        {
            for (int i = 1 ; i <= q ; ++i)
            {
                sparse[log][i] = sparse[log - 1][sparse[log - 1][i]];
            }
        }
    }

    int lift(int idx)
    {
        if (tree.findMAX(l[idx], r[idx]) > rank)
        {
            return 0;
        }

        int res = 1;
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (sparse[log][idx] != 0 && tree.findMAX(l[sparse[log][idx]], r[sparse[log][idx]]) <= rank)
            {
                res += (1 << log);
                idx = sparse[log][idx];
            }
        }

        return res;
    }
};

SparseLift sparseLift;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) 
{
    n = N;
    q = C;
    rank = R + 1;

    for (int i = 1 ; i < n ; ++i)
    {
        a[i] = K[i - 1] + 1;
        fenwick.update(i, 1);
    }

    a[n] = rank;
    fenwick.update(n, 1);
    tree.build();
    
    for (int i = 1 ; i <= q ; ++i)
    {
        int currL = S[i - 1] + 1;
        int currR = E[i - 1] + 1;
        int searchL = fenwick.findKth(currL);
        int searchR = fenwick.findKth(currR);
        if (leftFrom[searchL] != 0)
        {
            searchL = l[leftFrom[searchL]];
        }

        if (leftFrom[searchR] != 0)
        {
            searchR = r[leftFrom[searchR]];
        }

        for (int j = 0 ; j < currR - currL + 1 ; ++j)
        {
            int curr = fenwick.findKth(currL);
            if (first[curr] == 0) first[curr] = i;
            else
            {
                par[leftFrom[curr]] = i;
            }

            fenwick.update(curr, -1);
        }

        l[i] = searchL;
        r[i] = searchR;
        leftFrom[l[i]] = i;
        fenwick.update(l[i], 1);
    }
    
    sparseLift.build(par);
    int ans = sparseLift.lift(first[n]);
    int pos = n;

    for (int i = n ; i > 1 ; --i)
    {
        tree.update(i, a[i - 1]);
        tree.update(i - 1, rank);
        int curr = sparseLift.lift(first[i - 1]);
        if (curr >= ans)
        {
            pos = i - 1;
            ans = curr;
        }
    }

    return pos - 1;
}

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