oj.uz

Submission #777629

# Submission time Handle Problem Language Result Execution time Memory
777629 2023-07-09T11:34:35 Z boris_mihov Teams (IOI15_teams) C++17
100 / 100
 3399 ms 148984 KB 
#include "teams.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
#include <queue>

typedef long long llong;
const int MAXN = 500000 + 10;
const int INF = 1e9;

int n;
struct MST
{
    int a[MAXN];
    int b[MAXN];
    std::vector <int> tree[4*MAXN];

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

        int mid = (l + r) / 2;
        build(l, mid, 2*node);
        build(mid + 1, r, 2*node + 1);

        int lPtr = 0, rPtr = 0;
        tree[node].reserve(r - l + 1);
        for (int i = l ; i <= r ; ++i)
        {
            if (lPtr == tree[2*node].size())
            {
                tree[node].push_back(tree[2*node + 1][rPtr++]);
                continue;
            }

            if (rPtr == tree[2*node + 1].size())
            {
                tree[node].push_back(tree[2*node][lPtr++]);
                continue;
            }

            if (tree[2*node][lPtr] < tree[2*node + 1][rPtr])
            {
                tree[node].push_back(tree[2*node][lPtr++]);
            } else
            {
                tree[node].push_back(tree[2*node + 1][rPtr++]);
            }
        }
    }

    int binary(int node, int value)
    {
        int l = -1, r = tree[node].size(), mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (tree[node][mid] <= value) l = mid;
            else r = mid;
        }

        return r;
    }

    int query(int l, int r, int node, int queryL, int queryR, int valL, int valR)
    {
        if (r < queryL || queryR < l)
        {
            return 0;
        }

        if (queryL <= l && r <= queryR)
        {
            return binary(node, valR) - binary(node, valL - 1);
        }

        int mid = (l + r) / 2;
        return query(l, mid, 2*node, queryL, queryR, valL, valR) + query(mid + 1, r, 2*node + 1, queryL, queryR, valL, valR);
    }

    void build(int _a[], int _b[])
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            a[i] = _a[i];
            b[i] = _b[i];
        }

        build(1, n, 1);
    }

    int query(int l, int r, int valL, int valR)
    {
        if (l == 0 || r == 0  || valL > valR) return 0;
        return query(1, n, 1, l, r, valL, valR);
    }
};

int a[MAXN];
int b[MAXN];
int perm[MAXN];
int lastWithA[MAXN];
std::vector <int> v[MAXN];
MST tree;

void init(int N, int A[], int B[]) 
{
    n = N;
    std::iota(perm, perm + n, 0);
    std::sort(perm, perm + n, [&](int x, int y)
    {
        return A[x] < A[y] || (A[x] == A[y] && B[x] < B[y]);
    });

    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = A[perm[i - 1]];
        b[i] = B[perm[i - 1]];
        lastWithA[a[i]] = i;
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        lastWithA[i] = std::max(lastWithA[i], lastWithA[i - 1]);
    }

    // std::cout << "sorted\n";
    // for (int i = 1 ; i <= n ; ++i)
    // {
    //     std::cout << a[i] << ' ' << b[i] << '\n';
    // }

    tree.build(a, b);
}

struct StackElement
{
    int l;
    int r;
    int value;
    int left;
};

std::vector <StackElement> st;
int can(int M, int K[]) 
{
    st.clear();
    st.push_back({0, 0, INF, 0});
    std::sort(K, K + M);

    for (int i = 0 ; i < M ; ++i)
    {
        int want = K[i];
        int myValue = K[i];
        // std::cout << "i: " << i << ' ' << want << ' ' << lastWithA[K[i]] << '\n';
        
        while (!st.empty())
        {
            if (st.back().value < myValue)
            {
                st.pop_back();
                continue;
            }

            int myL = st.back().r + 1;
            int myR = lastWithA[K[i]];
            
            // std::cout << "try: " << myL << ' ' << myR << ' ' << myValue << ' ' << n << " = " << tree.query(myL, myR, myValue, n) << " ? " << want << '\n';
            if (tree.query(myL, myR, myValue, st.back().value) >= want)
            {
                int l = myValue - 1, r = n + 1, mid;
                while (l < r - 1)
                {
                    mid = (l + r) / 2;
                    if (tree.query(myL, myR, myValue, mid) < want) l = mid;
                    else r = mid;
                }

                st.push_back({myL, myR, r, tree.query(myL, myR, myValue, r) - want});
                break;
            }

            if (st.back().value >= myValue)
            {
                want += tree.query(st.back().l, st.back().r, myValue, st.back().value) - st.back().left;
            }

            st.pop_back();
        }

        // std::cout << "stack after: " << i << '\n';
        // for (const StackElement &curr : st)
        // {
        //     std::cout << curr.l << ' ' << curr.r << ' ' << curr.value << ' ' << curr.left << '\n';
        // }

        if (st.empty())
        {
            return 0;
        }
    }

    return 1;
}

Compilation message

teams.cpp: In member function 'void MST::build(int, int, int)':
teams.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             if (lPtr == tree[2*node].size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
teams.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             if (rPtr == tree[2*node + 1].size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In member function 'int MST::binary(int, int)':
teams.cpp:61:40: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   61 |         int l = -1, r = tree[node].size(), mid;
      |                         ~~~~~~~~~~~~~~~^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 59016 KB Output is correct
2 Correct 26 ms 59032 KB Output is correct
3 Correct 27 ms 59088 KB Output is correct
4 Correct 25 ms 59076 KB Output is correct
5 Correct 30 ms 59012 KB Output is correct
6 Correct 41 ms 59092 KB Output is correct
7 Correct 34 ms 59088 KB Output is correct
8 Correct 28 ms 59028 KB Output is correct
9 Correct 29 ms 59052 KB Output is correct
10 Correct 28 ms 58944 KB Output is correct
11 Correct 36 ms 59056 KB Output is correct
12 Correct 33 ms 59084 KB Output is correct
13 Correct 31 ms 59048 KB Output is correct
14 Correct 32 ms 59000 KB Output is correct
15 Correct 31 ms 58964 KB Output is correct
16 Correct 30 ms 59028 KB Output is correct
17 Correct 26 ms 59056 KB Output is correct
18 Correct 26 ms 59000 KB Output is correct
19 Correct 29 ms 59060 KB Output is correct
20 Correct 27 ms 59056 KB Output is correct
21 Correct 25 ms 58964 KB Output is correct
22 Correct 26 ms 58952 KB Output is correct
23 Correct 25 ms 59000 KB Output is correct
24 Correct 24 ms 59068 KB Output is correct
25 Correct 30 ms 59060 KB Output is correct
26 Correct 24 ms 58964 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 74828 KB Output is correct
2 Correct 69 ms 74820 KB Output is correct
3 Correct 64 ms 74796 KB Output is correct
4 Correct 65 ms 75292 KB Output is correct
5 Correct 59 ms 74336 KB Output is correct
6 Correct 54 ms 74420 KB Output is correct
7 Correct 56 ms 74392 KB Output is correct
8 Correct 73 ms 74380 KB Output is correct
9 Correct 87 ms 74652 KB Output is correct
10 Correct 202 ms 74276 KB Output is correct
11 Correct 89 ms 74196 KB Output is correct
12 Correct 53 ms 74264 KB Output is correct
13 Correct 58 ms 74496 KB Output is correct
14 Correct 59 ms 74524 KB Output is correct
15 Correct 62 ms 74516 KB Output is correct
16 Correct 62 ms 74532 KB Output is correct
17 Correct 75 ms 74572 KB Output is correct
18 Correct 54 ms 74568 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 75420 KB Output is correct
2 Correct 79 ms 75416 KB Output is correct
3 Correct 666 ms 78396 KB Output is correct
4 Correct 78 ms 75220 KB Output is correct
5 Correct 431 ms 75096 KB Output is correct
6 Correct 401 ms 75160 KB Output is correct
7 Correct 67 ms 75148 KB Output is correct
8 Correct 306 ms 75216 KB Output is correct
9 Correct 98 ms 74656 KB Output is correct
10 Correct 775 ms 74764 KB Output is correct
11 Correct 889 ms 74904 KB Output is correct
12 Correct 836 ms 75072 KB Output is correct
13 Correct 1061 ms 75596 KB Output is correct
14 Correct 1056 ms 77408 KB Output is correct
15 Correct 289 ms 75652 KB Output is correct
16 Correct 339 ms 75604 KB Output is correct
17 Correct 335 ms 75556 KB Output is correct
18 Correct 395 ms 75536 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 141120 KB Output is correct
2 Correct 307 ms 139964 KB Output is correct
3 Correct 2248 ms 145888 KB Output is correct
4 Correct 286 ms 139668 KB Output is correct
5 Correct 1321 ms 139700 KB Output is correct
6 Correct 1156 ms 139812 KB Output is correct
7 Correct 244 ms 139888 KB Output is correct
8 Correct 1042 ms 142732 KB Output is correct
9 Correct 513 ms 142812 KB Output is correct
10 Correct 2538 ms 141104 KB Output is correct
11 Correct 2437 ms 141700 KB Output is correct
12 Correct 2593 ms 142488 KB Output is correct
13 Correct 3399 ms 144044 KB Output is correct
14 Correct 3354 ms 148984 KB Output is correct
15 Correct 979 ms 145672 KB Output is correct
16 Correct 1002 ms 145396 KB Output is correct
17 Correct 990 ms 144808 KB Output is correct
18 Correct 1069 ms 144756 KB Output is correct