oj.uz

Submission #287248

# Submission time Handle Problem Language Result Execution time Memory
287248 2020-08-31T14:25:03 Z Kastanda Teams (IOI15_teams) C++11
100 / 100
 1478 ms 168640 KB 
// M
#include<bits/stdc++.h>
#include "teams.h"
using namespace std;
const int N = 500005 * 2, MXS = N * 19;
int n, A[N], B[N], K[N];
int ts, root[N], L[MXS], R[MXS], C[MXS];
vector < int > U, V[N];
int Add(int i, int id, int l = 1, int r = n + 1)
{
        int ID = ++ ts;
        L[ID] = L[id];
        R[ID] = R[id];
        C[ID] = C[id] + 1;
        if (r - l < 2)
                return ID;
        if (i < ((l + r) >> 1))
                L[ID] = Add(i, L[id], l, (l + r) >> 1);
        else
                R[ID] = Add(i, R[id], (l + r) >> 1, r);
        return ID;
}
int Count(int lid, int rid, int le, int ri, int l = 1, int r = n + 1)
{
        if (ri <= l || r <= le)
                return 0;
        if (le <= l && r <= ri)
                return C[rid] - C[lid];
        return Count(L[lid], L[rid], le, ri, l, (l + r) >> 1) + Count(R[lid], R[rid], le, ri, (l + r) >> 1, r);
}
int GetKth(int lid, int rid, int &k, int l = 1, int r = n + 1)
{
        if (C[rid] - C[lid] < k)
                return n + 1;
        if (r - l < 2)
                return l;
        if (C[L[rid]] - C[L[lid]] >= k)
                return GetKth(L[lid], L[rid], k, l, (l + r) >> 1);
        k -= C[L[rid]] - C[L[lid]];
        return GetKth(R[lid], R[rid], k, (l + r) >> 1, r);
}

void init(int _n, int _A[], int _B[])
{
        n = _n;
        vector < int > P(n);
        for (int i = 0; i < n; i ++)
                P[i] = i;
        sort(P.begin(), P.end(), [&](int i, int j){return make_pair(_B[i], _A[i]) < make_pair(_B[j], _A[j]);});

        U.push_back(0);
        for (int i = 0; i < n; i ++)
                U.push_back(_B[P[i]]);
        for (int i = 1; i <= n; i ++)
                A[i] = _A[P[i - 1]], B[i] = i;

        for (int i = 1; i <= n; i ++)
                V[A[i]].push_back(i);
        for (int i = 1; i <= n; i ++)
        {
                root[i] = root[i - 1];
                for (int j : V[i])
                        root[i] = Add(B[j], root[i]);
        }
}

int can(int _m, int _K[])
{
        int m = _m;
        for (int i = 1; i <= m; i ++)
                K[i] = _K[i - 1];

        sort(K + 1, K + m + 1);
        vector < pair < int , int > > Stk;
        Stk.push_back({0, n + 1});
        for (int i = 1; i <= m; i ++)
        {
                int need = K[i];
                int le = lower_bound(U.begin(), U.end(), K[i]) - U.begin();
                int ri = le;
                while (Stk.size() && need > 0)
                {
                        int c = Count(root[Stk.back().first], root[K[i]], ri, Stk.back().second);
                        if (c >= need)
                                break;
                        need -= c;
                        ri = max(ri, Stk.back().second);
                        Stk.pop_back();
                }
                if (!Stk.size())
                        return 0;
                assert(need);

                int c = Count(root[Stk.back().first], root[K[i]], 1, ri);
                need += c;
                ri = GetKth(root[Stk.back().first], root[K[i]], need);
                if (ri > n)
                        return 0;

                ri ++;
                assert(ri <= Stk.back().second);
                Stk.push_back({K[i], ri});
        }
        return 1;
}

Compilation message

teams.cpp: In function 'int can(int, int*)':
teams.cpp:79:64: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   79 |                 int le = lower_bound(U.begin(), U.end(), K[i]) - U.begin();
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 49096 KB Output is correct
2 Correct 105 ms 49136 KB Output is correct
3 Correct 106 ms 49136 KB Output is correct
4 Correct 107 ms 49520 KB Output is correct
5 Correct 59 ms 48112 KB Output is correct
6 Correct 58 ms 47932 KB Output is correct
7 Correct 58 ms 47856 KB Output is correct
8 Correct 58 ms 47984 KB Output is correct
9 Correct 76 ms 47856 KB Output is correct
10 Correct 63 ms 47856 KB Output is correct
11 Correct 53 ms 47856 KB Output is correct
12 Correct 55 ms 47856 KB Output is correct
13 Correct 66 ms 48016 KB Output is correct
14 Correct 67 ms 48368 KB Output is correct
15 Correct 93 ms 49008 KB Output is correct
16 Correct 96 ms 49008 KB Output is correct
17 Correct 60 ms 48060 KB Output is correct
18 Correct 58 ms 47856 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 49176 KB Output is correct
2 Correct 110 ms 49180 KB Output is correct
3 Correct 339 ms 52072 KB Output is correct
4 Correct 107 ms 49512 KB Output is correct
5 Correct 156 ms 47984 KB Output is correct
6 Correct 144 ms 47976 KB Output is correct
7 Correct 66 ms 47964 KB Output is correct
8 Correct 127 ms 47976 KB Output is correct
9 Correct 79 ms 47856 KB Output is correct
10 Correct 124 ms 47856 KB Output is correct
11 Correct 173 ms 47856 KB Output is correct
12 Correct 216 ms 47856 KB Output is correct
13 Correct 298 ms 48104 KB Output is correct
14 Correct 393 ms 50428 KB Output is correct
15 Correct 149 ms 49128 KB Output is correct
16 Correct 152 ms 49268 KB Output is correct
17 Correct 118 ms 47984 KB Output is correct
18 Correct 119 ms 48112 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 164008 KB Output is correct
2 Correct 715 ms 163816 KB Output is correct
3 Correct 1333 ms 168640 KB Output is correct
4 Correct 698 ms 164840 KB Output is correct
5 Correct 554 ms 158548 KB Output is correct
6 Correct 525 ms 158572 KB Output is correct
7 Correct 271 ms 158568 KB Output is correct
8 Correct 472 ms 158568 KB Output is correct
9 Correct 366 ms 157924 KB Output is correct
10 Correct 472 ms 158052 KB Output is correct
11 Correct 610 ms 157928 KB Output is correct
12 Correct 727 ms 157924 KB Output is correct
13 Correct 1070 ms 159192 KB Output is correct
14 Correct 1478 ms 165828 KB Output is correct
15 Correct 679 ms 163304 KB Output is correct
16 Correct 669 ms 163304 KB Output is correct
17 Correct 393 ms 163432 KB Output is correct
18 Correct 393 ms 163688 KB Output is correct