oj.uz

Submission #745363

# Submission time Handle Problem Language Result Execution time Memory
745363 2023-05-19T22:02:19 Z finn__ Teams (IOI15_teams) C++17
100 / 100
 3413 ms 61936 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 4 ms 4180 KB Output is correct
3 Correct 4 ms 4180 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4180 KB Output is correct
8 Correct 3 ms 4180 KB Output is correct
9 Correct 3 ms 4180 KB Output is correct
10 Correct 3 ms 4180 KB Output is correct
11 Correct 4 ms 4180 KB Output is correct
12 Correct 4 ms 4240 KB Output is correct
13 Correct 3 ms 4180 KB Output is correct
14 Correct 4 ms 4180 KB Output is correct
15 Correct 3 ms 4180 KB Output is correct
16 Correct 3 ms 4168 KB Output is correct
17 Correct 3 ms 4180 KB Output is correct
18 Correct 3 ms 4176 KB Output is correct
19 Correct 3 ms 4180 KB Output is correct
20 Correct 3 ms 4180 KB Output is correct
21 Correct 3 ms 4180 KB Output is correct
22 Correct 2 ms 4180 KB Output is correct
23 Correct 3 ms 4180 KB Output is correct
24 Correct 3 ms 4180 KB Output is correct
25 Correct 3 ms 4180 KB Output is correct
26 Correct 3 ms 4180 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 12280 KB Output is correct
2 Correct 162 ms 12224 KB Output is correct
3 Correct 156 ms 12260 KB Output is correct
4 Correct 161 ms 12588 KB Output is correct
5 Correct 67 ms 6648 KB Output is correct
6 Correct 67 ms 6728 KB Output is correct
7 Correct 67 ms 6728 KB Output is correct
8 Correct 65 ms 6648 KB Output is correct
9 Correct 34 ms 8260 KB Output is correct
10 Correct 32 ms 8140 KB Output is correct
11 Correct 32 ms 8092 KB Output is correct
12 Correct 44 ms 6704 KB Output is correct
13 Correct 66 ms 7176 KB Output is correct
14 Correct 111 ms 8512 KB Output is correct
15 Correct 132 ms 10868 KB Output is correct
16 Correct 132 ms 10792 KB Output is correct
17 Correct 40 ms 6728 KB Output is correct
18 Correct 40 ms 6728 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 12592 KB Output is correct
2 Correct 174 ms 12592 KB Output is correct
3 Correct 251 ms 15424 KB Output is correct
4 Correct 181 ms 12592 KB Output is correct
5 Correct 413 ms 7008 KB Output is correct
6 Correct 690 ms 7160 KB Output is correct
7 Correct 72 ms 7000 KB Output is correct
8 Correct 523 ms 6988 KB Output is correct
9 Correct 34 ms 8252 KB Output is correct
10 Correct 53 ms 8724 KB Output is correct
11 Correct 223 ms 8796 KB Output is correct
12 Correct 1306 ms 7064 KB Output is correct
13 Correct 604 ms 7488 KB Output is correct
14 Correct 315 ms 13716 KB Output is correct
15 Correct 206 ms 11236 KB Output is correct
16 Correct 210 ms 11184 KB Output is correct
17 Correct 183 ms 7088 KB Output is correct
18 Correct 169 ms 7088 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1204 ms 52136 KB Output is correct
2 Correct 1248 ms 52008 KB Output is correct
3 Correct 1507 ms 57896 KB Output is correct
4 Correct 1163 ms 52124 KB Output is correct
5 Correct 1996 ms 17480 KB Output is correct
6 Correct 3236 ms 21920 KB Output is correct
7 Correct 375 ms 21400 KB Output is correct
8 Correct 2421 ms 21860 KB Output is correct
9 Correct 175 ms 27492 KB Output is correct
10 Correct 346 ms 27736 KB Output is correct
11 Correct 2236 ms 28684 KB Output is correct
12 Correct 3413 ms 21564 KB Output is correct
13 Correct 1877 ms 26652 KB Output is correct
14 Correct 1663 ms 61936 KB Output is correct
15 Correct 935 ms 46616 KB Output is correct
16 Correct 927 ms 46680 KB Output is correct
17 Correct 506 ms 23860 KB Output is correct
18 Correct 475 ms 23976 KB Output is correct