Submission #362590

#	Time	Username	Problem	Language	Result	Execution time	Memory
362590		idk321	Jousting tournament (IOI12_tournament)	C++11	100 / 100	123 ms	16640 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

const int N = 100000;

int tree[4 * N];
int rmq[N][20];
array<int, 2> best[N];
list<int>::iterator to[N];
list<int> l;

int* rnk;
int n;

void cons()
{
    for (int i = 0; i < n - 1; i++)
    {
        rmq[i][0] = rnk[i];
    }
    for (int j = 1; j < 20; j++)
    {
        for (int i = 0; i + (1 << j) - 1 < n - 1; i++)
        {
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int getMax(int from, int to)
{
    for (int i = 19; i >= 0; i--)
    {
        if (from + (1 << i) - 1 <= to)
        {
            return max(rmq[from][i], rmq[to - (1 << i) + 1][i]);
        }
    }

    return -1;
}

void make(int num, int i, int a, int b, int node)
{
    if (a == b)
    {
        tree[node] = num;
        return;
    }

    int mid =(a + b) / 2;
    if (i <= mid) make(num, i, a, mid, node * 2);
    if (i > mid) make(num, i, mid + 1, b, node * 2 + 1);

    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int kth(int k, int a, int b, int node)
{
    if (a == b)
    {
        if (k == 0) return a;
        else return n;
    }

    int mid = (a + b) / 2;
    if (tree[node * 2] > k) return kth(k, a, mid, node * 2);
    return kth(k - tree[node * 2], mid + 1, b, node * 2 + 1);
}


int GetBestPosition(int xd, int c, int r, int *K, int *s, int *e) {
    n = xd;
    rnk = K;

    for (int i = 0; i < n; i++)
    {
         l.push_back(i);
         best[i] = {i, 0};
         make(1, i, 0, n - 1, 1);
    }

    int i = 0;
    auto it = l.begin();
    while (i < n)
    {
        to[i] = it;
        i++;
        it++;
    }

    cons();
    for (int i = 0; i < c; i++)
    {
        int a = s[i];
        int b = e[i];

        int x = kth(a, 0, n - 1, 1);
        int y = kth(b + 1, 0, n - 1, 1) - 1;
        int cur = getMax(x, y - 1);
        auto it = to[x];
        auto cbest = best[x];
        //cout << x << " " << y << endl;
        it++;
        while(it != l.end() && *it <= y)
        {
            if (best[*it][1] > cbest[1])
            {
                cbest = best[*it];
            }
            make(0, *it, 0, n - 1, 1);
            it = l.erase(it);
        }
        if (cur < r)cbest[1]++;
        best[x] = cbest;
    }

    auto res = best[0];
    for (int i = 1; i < n; i++)
    {
        if (best[i][1] > res[1]) res = best[i];
    }
    //cout << res[1] << endl;
    return res[0];
}

/*
5 3 3
1
0
2
4
1 3
0 1
0 1
*/

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