Submission #777629

#	Time	Username	Problem	Language	Result	Execution time	Memory
777629		boris_mihov	Teams (IOI15_teams)	C++17	100 / 100	3399 ms	148984 KiB

teams

#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 (stderr)

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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23