Submission #287248

#	Time	Username	Problem	Language	Result	Execution time	Memory
287248		Kastanda	Teams (IOI15_teams)	C++11	100 / 100	1478 ms	168640 KiB

teams

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

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