oj.uz

Submission #362602

# Submission time Handle Problem Language Result Execution time Memory
362602 2021-02-03T17:39:15 Z idk321 Jousting tournament (IOI12_tournament) C++11
100 / 100
 116 ms 12652 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100000;

int tree[4 * N];
int lazy[4 * N];
int tree2[4 * N];
int rmq[N][20];

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 push(int node, int a, int mid, int b)
{
    if (lazy[node] != -1)
    {
        tree[node * 2] = (mid - a + 1) * lazy[node];
        tree[node * 2 + 1] = (b - mid) * lazy[node];
        lazy[node * 2] = lazy[node];
        lazy[node * 2 + 1] = lazy[node];
        lazy[node] = -1;
    }

}

void add(int num, int from, int to, int a, int b, int node)
{
    if (from <= a && b <= to)
    {
        tree2[node] += num;
        return;
    }

    int mid = (a + b) / 2;
    if (from <= mid) add(num, from, to, a, mid, node * 2);
    if (to > mid) add(num, from, to, mid + 1, b, node * 2 + 1);
}

int getSum(int i, int a, int b, int node)
{
    if (a == b)
    {
        return tree2[node];
    }

    int cur = 0;
    int mid = (a + b) / 2;
    if (i <= mid) cur = getSum(i, a, mid, node * 2);
    if (i > mid) cur = getSum(i, mid + 1, b, node * 2 + 1);
    return cur + tree2[node];
}

void make(int num, int from, int to, int a, int b, int node)
{
    if (from <= a && b <= to)
    {
        tree[node] = (b - a + 1) * num; //B - A ne FROM - TO TI RETARD
        lazy[node] = num;
        return;
    }

    int mid =(a + b) / 2;
    push(node, a, mid, b);
    if (from <= mid) make(num, from, to, a, mid, node * 2);
    if (to > mid) make(num, from, to, 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;
    push(node, a, mid, b);
    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 < 4 * N; i++)
    {
        lazy[i] = -1;
    }
    for (int i = 0; i < n; i++)
    {

         make(1, 0, n - 1, 0, n - 1, 1);
    }


    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);
        //cout << cur << " " << r << endl;
        //cout << x << " " << y << endl;
        make(0, x + 1, y, 0, n - 1, 1);
        if (cur < r) add(1, x, y, 0, n - 1, 1);

    }

    array<int, 2> res = {-1, -1};
    for (int i = 0; i < n; i++)
    {
        int cur = getSum(i, 0, n - 1, 1);
        if (cur > res[1])
        {
            res = {i, cur};
        }
    }
    //cout << res[1] << endl;
    return res[0];
}

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

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2028 KB Output is correct
2 Correct 6 ms 2412 KB Output is correct
3 Correct 3 ms 2412 KB Output is correct
4 Correct 6 ms 2412 KB Output is correct
5 Correct 6 ms 2412 KB Output is correct
6 Correct 5 ms 2412 KB Output is correct
7 Correct 6 ms 2412 KB Output is correct
8 Correct 6 ms 2412 KB Output is correct
9 Correct 3 ms 2284 KB Output is correct
10 Correct 6 ms 2540 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7276 KB Output is correct
2 Correct 111 ms 12268 KB Output is correct
3 Correct 39 ms 10476 KB Output is correct
4 Correct 116 ms 12396 KB Output is correct
5 Correct 108 ms 12140 KB Output is correct
6 Correct 100 ms 12652 KB Output is correct
7 Correct 113 ms 12524 KB Output is correct
8 Correct 113 ms 12396 KB Output is correct
9 Correct 35 ms 10220 KB Output is correct
10 Correct 39 ms 11756 KB Output is correct