Submission #585071

#	Time	Username	Problem	Language	Result	Execution time	Memory
585071		snokes	Teams (IOI15_teams)	C++17	34 / 100	4100 ms	55044 KiB

teams

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

const int mxN = 5e5 + 5;
vector<int> until[mxN];
int N;

void init(int _N, int A[], int B[])
{
    N = _N;
    for(int i = 0; i < N; i++) until[A[i]].push_back(B[i]);
}

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

    multiset<int> avilable;
    for(int i = 0, j = 0; i < M; i++)
    {
        while(j < N && j <= K[i])
        {
            for(int x : until[j])
            {
                avilable.insert(x);
            }
            j++;
        }

        int rem = K[i];
        while(rem > 0 && !avilable.empty())
        {
            int me = *avilable.begin();
            avilable.erase(avilable.begin());
            if(me < K[i]) continue;
            rem--;
        }
        assert(rem >= 0);
        if(rem != 0)
        {
            return 0;
        }
    }
    return 1;
}

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