Submission #287203

#	Time	Username	Problem	Language	Result	Execution time	Memory
287203		stoyan_malinin	Jousting tournament (IOI12_tournament)	C++14	100 / 100	175 ms	35448 KiB

tournament

//#include "grader.cpp"

#include <tuple>
#include <random>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

const int MAXLog = 18;
const int MAXN = 2e5 + 5;

mt19937 rnd(22);

struct SparseTable
{
    int n;
    int logVal[MAXN];
    int sparse[25][MAXN];

    SparseTable(){}
    SparseTable(int n, int *a)
    {
        this->n = n;
        this->init(a);
    }

    void init(int *a)
    {
        logVal[0] = logVal[1] = 0;
        for(int i = 2;i<=n;i++) logVal[i] = logVal[i/2] + 1;

        for(int i = 0;i<n;i++) sparse[0][i] = a[i];
        for(int step = 1;step<=MAXLog;step++)
        {
            for(int i = 0;i<n;i++)
            {
                if(i+(1<<(step-1))<n)
                {
                    sparse[step][i] = max(sparse[step-1][i], sparse[step-1][i+(1<<(step-1))]);
                }
                else
                {
                    sparse[step][i] = sparse[step-1][i];
                }
            }
        }
    }

    int getMax(int l, int r)
    {
        if(l>r) return -1;

        int log2 = logVal[r-l+1];
        return max(sparse[log2][l], sparse[log2][r-(1<<log2)+1]);
    }
};

struct Treap
{
    int length;
    pair <int, int> seg;

    int treeInd;

    int priority;
    Treap *L, *R;

    Treap()
    {
        this->length = 1;
        this->priority = rnd();

        this->L = nullptr;
        this->R = nullptr;
    }
    Treap(pair <int, int> seg, int treeInd)
    {
        this->treeInd = treeInd;

        this->seg = seg;
        this->length = 1;
        this->priority = rnd();

        this->L = nullptr;
        this->R = nullptr;
    }

    void recalc()
    {
        length = 1;
        if(L!=nullptr) length += L->length;
        if(R!=nullptr) length += R->length;
    }
};

Treap *Merge(Treap *small,  Treap *big)
{
    if(small==nullptr) return big;
    if(big==nullptr) return small;

    if(small->priority > big->priority)
    {
        small->R = Merge(small->R, big);
        small->recalc();

        return small;
    }
    else
    {
        big->L = Merge(small, big->L);
        big->recalc();

        return big;
    }
}

pair <Treap*, Treap*> SplitSz(Treap *T, int sz)
{
    if(T==nullptr) return {nullptr, nullptr};
    if(sz==0) return {nullptr, T};

    int leftSz = ((T->L==nullptr)?0:T->L->length);
    if(1+leftSz<=sz)
    {
        auto splitResult = SplitSz(T->R, sz-leftSz-1);

        T->R = splitResult.first;
        T->recalc();

        return {T, splitResult.second};
    }
    else
    {
        auto splitResult = SplitSz(T->L, sz);

        T->L = splitResult.second;
        T->recalc();

        return {splitResult.first, T};
    }
}

struct Tree
{
    struct Node
    {
        int x;
        int l, r;

        int maxDepth;

        Node(){}
        Node(int x)
        {
            this->x = x;

            this->l = MAXN;
            this->r = -1;
        }
        Node(int x, int l, int r)
        {
            this->x = x;
            this->l = l;
            this->r = r;
        }
    };

    Node a[MAXN];
    vector <int> children[MAXN];

    void addNode(Node x)
    {
        a[x.x] = x;
    }

    void addChild(int parent, int child)
    {
        children[parent].push_back(child);
    }

    void dfsInit(int x)
    {
        sort(children[x].begin(), children[x].end(),
        [&](int A, int B)
        {
            if(a[A].l!=a[B].l) return a[A].l<a[B].l;
            return a[A].r<a[B].r;
        });

        a[x].maxDepth = 0;
        for(int y: children[x])
        {
            dfsInit(y);
            a[x].maxDepth = max(a[x].maxDepth, a[y].maxDepth+1);
        }

        //cout << a[x].l << " " << a[x].r << " -> " << a[x].maxDepth << '\n';
    }

    int getMax(int l, int r, int *k)
    {
        int maxVal = 0;
        for(int i = l;i<=r;i++) maxVal = max(maxVal, k[i]);

        return maxVal;
    }

    pair <int, int> findBest(int x, int r, SparseTable &sparse)
    {
        //-cout << a[x].l << " " << a[x].r << " -> " << a[x].maxDepth << " || "
        //<< sparse.getMax(a[x].l, a[x].r-1) << '\n';
        if(sparse.getMax(a[x].l, a[x].r-1)<r) return {a[x].maxDepth, -a[x].l};

        pair <int, int> ans = {-1, -1};
        for(int y: children[x])
            ans = max(ans, findBest(y, r, sparse));


        return ans;
    }

    int getAns(int x, int depth)
    {
        if(depth==0) return a[x].l;

        for(int y: children[x])
        {
            if(a[y].maxDepth==depth-1) return getAns(y, depth-1);
        }
    }

    int findNode(int all, int l, int maxDepth)
    {
        for(int i = 0;i<all;i++)
        {
            if(a[i].l==l && a[i].maxDepth==maxDepth) return i;
        }
    }
};

int n;
int k[MAXN];

Tree yoanko;

tuple <Treap*, Treap*, Treap*> splitBySegment(Treap *&T, int l, int r)
{
    auto help1 = SplitSz(T, l);
    auto help2 = SplitSz(help1.second, r-l+1);

    return make_tuple(help1.first, help2.first, help2.second);
}

Treap *createReplacement(Treap *T, int newInd, vector <int> &children)
{
    Treap *out = new Treap();

    out->treeInd = newInd;
    out->seg = {MAXN, -1};

    function <void(Treap*)> use = [&](Treap *T)
    {
        children.push_back(T->treeInd);
        out->seg.first = min(out->seg.first, T->seg.first);
        out->seg.second = max(out->seg.second, T->seg.second);

        if(T->L!=nullptr) use(T->L);
        if(T->R!=nullptr) use(T->R);
    };

    use(T);
    return out;
}

void constructTree(int c, int *s, int *e)
{
    Treap *T = nullptr;
    for(int i = 0;i<n;i++)
    {
        Treap *add = new Treap(make_pair(i, i), i);
        yoanko.addNode(Tree::Node(i, i, i));

        T = Merge(T, add);
    }

    for(int i = 0;i<c;i++)
    {
        auto help = splitBySegment(T, s[i], e[i]);

        Treap *part1 = get<0>(help);
        Treap *part2 = get<1>(help);
        Treap *part3 = get<2>(help);

        //if(part1!=nullptr) cout << " " << part1->length;
        //if(part2!=nullptr) cout << " " << part2->length;
        //if(part3!=nullptr) cout << " " << part3->length;
        //cout << '\n';

        vector <int> children;
        Treap *replacement = createReplacement(part2, n+i, children);

        yoanko.addNode(Tree::Node(n+i, replacement->seg.first, replacement->seg.second));
        for(int child: children) yoanko.addChild(n+i, child);

        //cout << replacement->seg.first << " " << replacement->seg.second << '\n';

        T = Merge(part1, Merge(replacement, part3));
    }

    //cout << " --- " << '\n';
    yoanko.dfsInit(n+c-1);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
    n = N;
    for(int i = 0;i<n;i++) k[i] = K[i];

    constructTree(C, S, E);

    SparseTable sparse = SparseTable(N, K);
    pair <int, int> raw = yoanko.findBest(N+C-1, R, sparse);
    //cout << raw.first << '\n';

    return yoanko.getAns(yoanko.findNode(N+C, -raw.second, raw.first), raw.first);
}

Compilation message (stderr)

tournament.cpp: In member function 'int Tree::findNode(int, int, int)':
tournament.cpp:241:5: warning: control reaches end of non-void function [-Wreturn-type]
  241 |     }
      |     ^
tournament.cpp: In member function 'int Tree::getAns(int, int)':
tournament.cpp:233:5: warning: control reaches end of non-void function [-Wreturn-type]
  233 |     }
      |     ^

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