Submission #126064

#	Time	Username	Problem	Language	Result	Execution time	Memory
126064		dragonslayerit	Teams (IOI15_teams)	C++14	34 / 100	4103 ms	38948 KiB

teams

#include "teams.h"
#include <vector>
#include <set>

std::vector<int> right[500005];
int NN;

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

int can(int M, int K[]) {
  std::vector<int> freq(NN+1);
  int sum=0;
  for(int i=0;i<M;i++){
    freq[K[i]]+=K[i];
    sum+=K[i];
    if(sum>NN) return 0;
  }
  std::multiset<int> active;
  for(int i=1;i<=NN;i++){
    for(int v:right[i]){
      active.insert(v);
    }
    while(active.size()&&*active.begin()<i) active.erase(active.begin());
    while(freq[i]--){
      if(active.empty()) return 0;
      active.erase(active.begin());
    }
  }
  return 1;
}

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