Submission #1211778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211778		XCAC197	Teams (IOI15_teams)	C++20	0 / 100	4091 ms	12256 KiB

teams

//#include "teams.h"
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N;
pair<int,int> ivs [500000];

void init(int N_, int A_[], int B_[]) {
    N = N_;
    for(int i = 0; i < N; i++){
        ivs[i] = make_pair(A_[i], B_[i]);
    }
    sort(ivs, ivs+N);
}

int can(int M, int K[]) {
	//always elect to eat the intervals that end first
    //insertion events happen randomly, but deletion events ordered (Assuming sort by right endpoint?)
    
    //prediction: Something related to sqrt() happens?
    //l, r
    sort(K, K+M);
    int su = 0;
    for(int i = 0; i < M; i++){
        su += K[i];
    }
    if(su >= N){
        return 0;
    }else{
        priority_queue <int, vector<int>, greater <int>> pq;
        int cptr = 0;
        for(int i = 0; i < M; i++){
            while(cptr < N && ivs[cptr].first <= K[i]){
                pq.push(ivs[cptr].second);
                cptr++;
            }
            //remove not useful students
            while(!pq.empty() && (pq.top()) < K[i]){
                pq.pop();
            }
            if(pq.size() < K[i]){
                return 0;
            }else{
                for(int j = 0; j < K[i]; j++){
                    pq.pop();
                }
            }
        }
        return 1;
    }
}

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