Submission #726668

#	Time	Username	Problem	Language	Result	Execution time	Memory
726668		TheSahib	Teams (IOI15_teams)	C++17	34 / 100	4033 ms	38948 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>

using namespace std;

int n;
vector<pii> v;

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


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

    vector<pii> events[n + 1];
    for (int i = 0; i < n; i++)
    {
        events[v[i].first].push_back({0, i});
        if(v[i].second + 1 <= n){
            events[v[i].second + 1].push_back({1, i});
        }
    }

    
    
    int j = 0;
    multiset<pii> s;
    for (int x = 0; x <= n && j < M; x++)
    {
        for(auto& e:events[x]){
            if(e.first == 0){
                s.insert({v[e.second].second, v[e.second].first});
            }
            else{
                auto itr = s.find({v[e.second].second, v[e.second].first});
                if(itr != s.end()){
                    s.erase(itr);
                }
            }
        }
        while(x == K[j]){
            if(s.size() < K[j]){
                return false;
            }
            for (int i = 0; i < K[j]; i++)
            {
                s.erase(s.begin());
            }
            ++j;
            if(j == M) break;
        }
    }
    return true;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:53:25: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |             if(s.size() < K[j]){
      |                ~~~~~~~~~^~~~~~

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