Submission #745363

#	Time	Username	Problem	Language	Result	Execution time	Memory
745363		finn__	Teams (IOI15_teams)	C++17	100 / 100	3413 ms	61936 KiB

teams

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,sse4")

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

template <typename T, int64_t N, int64_t M>
struct FenwickTree2dOff
{
    T t[M];
    vector<pair<unsigned, unsigned>> coords;
    unsigned b[N + 1], c[M];

    void add_coordinate(int64_t i, int64_t j) { coords.emplace_back(i, j); }

    void initialize()
    {
        sort(coords.begin(), coords.end(), [](auto const &a, auto const &b)
             { return a.second < b.second; });
        memset(t, 255, N * sizeof *t);
        for (auto const &[x, y] : coords)
            for (int64_t i = x + 1; i <= N; i += i & -i)
                b[i - 1] += (t[i - 1] != y), t[i - 1] = y;
        for (size_t i = 1; i < N; ++i)
            b[i] += b[i - 1];
        memset(t, 255, N * sizeof *t);
        reverse(coords.begin(), coords.end());
        for (auto const &[x, y] : coords)
            for (int64_t i = x + 1; i <= N; i += i & -i)
                if (t[i - 1] != y)
                    c[--b[i - 1]] = y, t[i - 1] = y;
        memset(t, 0, N * sizeof *t);
    }

    void update(int64_t i, int64_t j, T x)
    {
        ++i;
        while (i <= N)
        {
            int64_t k = upper_bound(c + b[i - 1], c + b[i], j) - (c + b[i - 1]);
            while (k <= b[i] - b[i - 1])
                t[b[i - 1] + k - 1] += x, k += k & -k;
            i += i & -i;
        }
    }

    T prefix_sum(int64_t i, int64_t j)
    {
        ++i;
        T x = 0;
        while (i)
        {
            int64_t k = upper_bound(c + b[i - 1], c + b[i], j) - (c + b[i - 1]);
            while (k)
                x += t[b[i - 1] + k - 1], k -= k & -k;
            i -= i & -i;
        }
        return x;
    }

    T range_sum(int64_t i1, int64_t i2, int64_t j1, int64_t j2)
    {
        return prefix_sum(i2, j2) - (i1 ? prefix_sum(i1 - 1, j2) : 0) -
               (j1 ? prefix_sum(i2, j1 - 1) : 0) +
               (i1 && j1 ? prefix_sum(i1 - 1, j1 - 1) : 0);
    }
};

constexpr size_t MaxN = 500009, Block = 300, TreeSize = 6000000;

FenwickTree2dOff<int, MaxN, TreeSize> tree;

size_t n;
pair<int, int> pupils[MaxN];

void init(int N, int A[], int B[])
{
    for (size_t i = 0; i < N; ++i)
        tree.add_coordinate(A[i], B[i]), pupils[i] = {A[i], B[i]};
    tree.initialize();
    for (size_t i = 0; i < N; ++i)
        tree.update(A[i], B[i], 1);
    n = N;
    sort(pupils, pupils + n);
}

int can(int M, int K[])
{
    sort(K, K + M);

    if (M > Block)
    {
        size_t j = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        for (size_t i = 0; i < M; ++i)
        {
            while (j < n && pupils[j].first <= K[i])
                q.emplace(pupils[j].second, pupils[j].first), ++j;
            while (!q.empty() && q.top().first < K[i])
                q.pop();
            if (q.size() < K[i])
                return 0;
            while (K[i]--)
                q.pop();
        }
    }
    else
    {
        vector<int64_t> f(M);
        for (size_t i = 0; i < M; ++i)
        {
            f[i] = tree.range_sum(0, K[i], K[i], MaxN - 1) - K[i];
            for (size_t j = 0; j < i && f[i] >= 0; ++j)
                f[i] = min(f[i], f[j] + (K[i] == K[j] ? 0 : tree.range_sum(K[j] + 1, K[i], K[i], MaxN - 1)) - K[i]);
            if (f[i] < 0)
                return 0;
        }
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In lambda function:
teams.cpp:19:74: warning: declaration of 'b' shadows a member of 'FenwickTree2dOff<T, N, M>' [-Wshadow]
   19 |         sort(coords.begin(), coords.end(), [](auto const &a, auto const &b)
      |                                                              ~~~~~~~~~~~~^
teams.cpp:13:14: note: shadowed declaration is here
   13 |     unsigned b[N + 1], c[M];
      |              ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:79:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |     for (size_t i = 0; i < N; ++i)
      |                        ~~^~~
teams.cpp:82:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |     for (size_t i = 0; i < N; ++i)
      |                        ~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:92:11: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   92 |     if (M > Block)
      |         ~~^~~~~~~
teams.cpp:96:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |         for (size_t i = 0; i < M; ++i)
      |                            ~~^~~
teams.cpp:102:26: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |             if (q.size() < K[i])
      |                 ~~~~~~~~~^~~~~~
teams.cpp:111:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |         for (size_t i = 0; i < M; ++i)
      |                            ~~^~~
teams.cpp: In instantiation of 'void FenwickTree2dOff<T, N, M>::initialize() [with T = int; long int N = 500009; long int M = 6000000]':
teams.cpp:81:21:   required from here
teams.cpp:19:74: warning: declaration of 'b' shadows a member of 'FenwickTree2dOff<int, 500009, 6000000>' [-Wshadow]
   19 |         sort(coords.begin(), coords.end(), [](auto const &a, auto const &b)
      |                                                              ~~~~~~~~~~~~^
teams.cpp:13:14: note: shadowed declaration is here
   13 |     unsigned b[N + 1], c[M];
      |              ^
teams.cpp:24:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::tuple_element<1, const std::pair<unsigned int, unsigned int> >::type' {aka 'const unsigned int'} [-Wsign-compare]
   24 |                 b[i - 1] += (t[i - 1] != y), t[i - 1] = y;
      |                             ~~~~~~~~~~^~~~~
teams.cpp:31:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::tuple_element<1, const std::pair<unsigned int, unsigned int> >::type' {aka 'const unsigned int'} [-Wsign-compare]
   31 |                 if (t[i - 1] != y)
      |                     ~~~~~~~~~^~~~
teams.cpp: In instantiation of 'FenwickTree2dOff<T, N, M>::initialize<int, 500009, 6000000>::<lambda(const auto:23&, const auto:24&)> [with auto:23 = std::pair<unsigned int, unsigned int>; auto:24 = std::pair<unsigned int, unsigned int>]':
/usr/include/c++/10/bits/predefined_ops.h:156:30:   required from 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int> > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int> > >; _Compare = FenwickTree2dOff<T, N, M>::initialize<int, 500009, 6000000>::<lambda(const auto:23&, const auto:24&)>]'
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<FenwickTree2dOff<T, N, M>::initialize<int, 500009, 6000000>::<lambda(const auto:23&, const auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<FenwickTree2dOff<T, N, M>::initialize<int, 500009, 6000000>::<lambda(const auto:23&, const auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int> > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<FenwickTree2dOff<T, N, M>::initialize<int, 500009, 6000000>::<lambda(const auto:23&, const auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<FenwickTree2dOff<T, N, M>::initialize<int, 500009, 6000000>::<lambda(const auto:23&, const auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int> > >; _Compare = FenwickTree2dOff<T, N, M>::initialize<int, 500009, 6000000>::<lambda(const auto:23&, const auto:24&)>]'
teams.cpp:19:13:   required from 'void FenwickTree2dOff<T, N, M>::initialize() [with T = int; long int N = 500009; long int M = 6000000]'
teams.cpp:81:21:   required from here
teams.cpp:19:74: warning: declaration of 'b' shadows a member of 'FenwickTree2dOff<int, 500009, 6000000>' [-Wshadow]
   19 |         sort(coords.begin(), coords.end(), [](auto const &a, auto const &b)
      |                                                              ~~~~~~~~~~~~^
teams.cpp:13:14: note: shadowed declaration is here
   13 |     unsigned b[N + 1], c[M];
      |              ^

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23