oj.uz

Submission #938023

# Submission time Handle Problem Language Result Execution time Memory
938023 2024-03-04T18:04:18 Z danikoynov Teams (IOI15_teams) C++14
100 / 100
 2388 ms 361548 KB 
#include "teams.h"

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct segment
{
    int l, r;

    segment(int _l = 0, int _r = 0)
    {
        l = _l;
        r = _r;
    }
};

const int maxn = 5e5 + 10;

struct node
{
    node *lc, *rc;
    int sum;

    node(int _sum = 0)
    {
        lc = rc = NULL;
        sum = _sum;
    }
};

node *update(node *root, int left, int right, int pivot)
{

    if (left == right)
    {
        int val = 1;
        if (root != NULL)
            val += root -> sum;
        return new node(val);
    }

    int mid = (left + right) / 2;
    node *new_root = new node();
    if (root != NULL)
    {
        new_root -> lc = root -> lc; /// try to change this
        new_root -> rc = root -> rc;
    }

    if (pivot <= mid)
        new_root -> lc = update(new_root -> lc, left, mid, pivot);
    else
        new_root -> rc = update(new_root -> rc, mid + 1, right, pivot);

    new_root -> sum = 0;
    if (new_root -> lc != NULL)
        new_root -> sum += new_root -> lc -> sum;
    if (new_root -> rc != NULL)
        new_root -> sum += new_root -> rc -> sum;
    return new_root;
}

int query(node *root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft || root == NULL)
        return 0;

    if (left >= qleft && right <= qright)
        return root -> sum;

    int mid = (left + right) / 2;
    return query(root -> lc, left, mid, qleft, qright) +
           query(root -> rc, mid + 1, right, qleft, qright);
}

int n;
segment s[maxn];
node *root[maxn];
vector < int > upd[maxn];
void init(int N, int A[], int B[])
{
    n = N;
    for (int i = 1; i <= n; i ++)
    {
        s[i] = segment(A[i - 1], B[i - 1]);
        upd[A[i - 1]].push_back(B[i - 1]);
    }

    root[0] = NULL;
    for (int i = 1; i <= n; i ++)
    {
        root[i] = root[i - 1];
        for (int pivot : upd[i])
        {
            root[i] = update(root[i], 1, n, pivot);
        }
    }

    ///exit(0);
}


int zeta(int a, int b)
{
    if (a >= b)
    return 0;
    return query(root[b], 1, n, b, n) - query(root[a], 1, n, b, n);
    /**int cnt = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (s[i].l <= a && s[i].r >= a)
            continue;
        if (s[i].l <= b && s[i].r >= b)
            cnt ++;
    }
    return cnt;*/
}

int pivot_change(int a, int b, int diff)
{
    /// dp_a + z(a, i) > dp_b + z(b, i)
    /// dp_b - dp_a < z(a, i) - z(b, i)
    /// diff < ....
    int lf = b, rf = n;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (diff < zeta(a, mf) - zeta(b, mf))
            lf = mf + 1;
        else
            rf = mf - 1;
    }
    return lf;
}

int dp[maxn];
int can(int M, int K[])
{
    sort(K, K + M);
    set < int > act;
    set < pair < int, int > > event;

    for (int i = 0; i < M; i ++)
    {
        while(!event.empty() && (*event.begin()).first <= K[i])
        {
            set < int > :: iterator it = act.find((*event.begin()).second);
            event.erase({pivot_change(K[*prev(it)], K[*it], dp[*it] - dp[*prev(it)]), *it});
            if (next(it) != act.end())
            {
                event.erase({pivot_change(K[*it], K[*next(it)], dp[*next(it)] - dp[*it]), *next(it)});
                event.insert({pivot_change(K[*prev(it)], K[*next(it)], dp[*next(it)] - dp[*prev(it)]), *next(it)});
            }
            act.erase(it);
        }
        dp[i] = zeta(0, K[i]) - K[i];
        if (!act.empty())
        {
            int bk = *act.rbegin();
            dp[i] = min(dp[i], dp[bk] + zeta(K[bk], K[i]) - K[i]);
        }
        /**for (int j : act)
        {
            dp[i] = min(dp[i], dp[j] + zeta(K[j], K[i]) - K[i]);
        }*/
        if (dp[i] < 0)
            return 0;

        if (!act.empty())
        {
            int bk = *act.rbegin();
            event.insert({pivot_change(K[bk], K[i], dp[i] - dp[bk]), i});
        }
        act.insert(i);
    }
    return 1;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19548 KB Output is correct
2 Correct 4 ms 19548 KB Output is correct
3 Correct 4 ms 19640 KB Output is correct
4 Correct 4 ms 19748 KB Output is correct
5 Correct 4 ms 19544 KB Output is correct
6 Correct 6 ms 19804 KB Output is correct
7 Correct 6 ms 19548 KB Output is correct
8 Correct 5 ms 19548 KB Output is correct
9 Correct 4 ms 19544 KB Output is correct
10 Correct 4 ms 19744 KB Output is correct
11 Correct 4 ms 19544 KB Output is correct
12 Correct 7 ms 19708 KB Output is correct
13 Correct 5 ms 19640 KB Output is correct
14 Correct 5 ms 19548 KB Output is correct
15 Correct 4 ms 19548 KB Output is correct
16 Correct 5 ms 19548 KB Output is correct
17 Correct 6 ms 19548 KB Output is correct
18 Correct 5 ms 19548 KB Output is correct
19 Correct 4 ms 19800 KB Output is correct
20 Correct 4 ms 19748 KB Output is correct
21 Correct 4 ms 19548 KB Output is correct
22 Correct 4 ms 19764 KB Output is correct
23 Correct 4 ms 19752 KB Output is correct
24 Correct 4 ms 19548 KB Output is correct
25 Correct 4 ms 19548 KB Output is correct
26 Correct 4 ms 19548 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 78676 KB Output is correct
2 Correct 90 ms 78800 KB Output is correct
3 Correct 86 ms 78836 KB Output is correct
4 Correct 106 ms 79444 KB Output is correct
5 Correct 62 ms 77272 KB Output is correct
6 Correct 61 ms 77064 KB Output is correct
7 Correct 63 ms 77268 KB Output is correct
8 Correct 60 ms 77136 KB Output is correct
9 Correct 162 ms 78268 KB Output is correct
10 Correct 69 ms 76264 KB Output is correct
11 Correct 60 ms 78020 KB Output is correct
12 Correct 59 ms 74696 KB Output is correct
13 Correct 66 ms 78612 KB Output is correct
14 Correct 67 ms 76356 KB Output is correct
15 Correct 89 ms 78568 KB Output is correct
16 Correct 78 ms 78672 KB Output is correct
17 Correct 63 ms 78416 KB Output is correct
18 Correct 63 ms 78164 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 79444 KB Output is correct
2 Correct 95 ms 79368 KB Output is correct
3 Correct 149 ms 82840 KB Output is correct
4 Correct 96 ms 79396 KB Output is correct
5 Correct 621 ms 77908 KB Output is correct
6 Correct 546 ms 77904 KB Output is correct
7 Correct 65 ms 77792 KB Output is correct
8 Correct 432 ms 78052 KB Output is correct
9 Correct 163 ms 78204 KB Output is correct
10 Correct 130 ms 76908 KB Output is correct
11 Correct 130 ms 78536 KB Output is correct
12 Correct 153 ms 75464 KB Output is correct
13 Correct 276 ms 79272 KB Output is correct
14 Correct 561 ms 80888 KB Output is correct
15 Correct 741 ms 79476 KB Output is correct
16 Correct 696 ms 79572 KB Output is correct
17 Correct 677 ms 79436 KB Output is correct
18 Correct 700 ms 79108 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 353796 KB Output is correct
2 Correct 614 ms 354640 KB Output is correct
3 Correct 840 ms 361548 KB Output is correct
4 Correct 603 ms 355048 KB Output is correct
5 Correct 1759 ms 346368 KB Output is correct
6 Correct 1536 ms 346044 KB Output is correct
7 Correct 333 ms 345940 KB Output is correct
8 Correct 1303 ms 346448 KB Output is correct
9 Correct 968 ms 346412 KB Output is correct
10 Correct 458 ms 346304 KB Output is correct
11 Correct 485 ms 345256 KB Output is correct
12 Correct 564 ms 346304 KB Output is correct
13 Correct 1132 ms 349352 KB Output is correct
14 Correct 2388 ms 355636 KB Output is correct
15 Correct 2268 ms 353820 KB Output is correct
16 Correct 2146 ms 353804 KB Output is correct
17 Correct 2054 ms 348672 KB Output is correct
18 Correct 2001 ms 349464 KB Output is correct