#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
#include "teams.h"
const int MAX = 1e5 + 5; // change to 1e5 + 5 later
int N;
vector<ii> allp;
void init(int N_g, int A_g[], int B_g[]) {
N = N_g;
for (int i = 0; i < N; i++) {
allp.pb({A_g[i], B_g[i]});
}
}
int can(int M, int K_g[]) {
vi teams;
for (int i = 0; i < M; i++) {
teams.pb(K_g[i]);
}
sort(teams.begin(), teams.end());
multiset<int> tr1[MAX]; // all end with start equal to i
multiset<int> tr2[MAX]; // all start with end equal to i
for (ii p : allp) {
tr1[p.fi].insert(p.se);
tr2[p.se].insert(p.fi);
}
multiset<ii> have; // all eligible {end, start}
// at each time, get best
int curr = 0; // minimum start
for (int i = 0; i < M; i++) {
// cout<<"at "<<i<<endl;
for (int j = curr + 1; j <= teams[i]; j++) { // add starting w/ j
for (int x : tr1[j]) {
// cout<<"inserting "<<x<<" "<<j<<endl;
have.insert({x, j});
}
}
for (int j = curr; j < teams[i]; j++) { // remove ending w/ j
for (int x : tr2[j]) {
have.erase(have.find({j, x}));
}
tr2[j].clear();
}
curr = teams[i];
for (int j = 0; j < teams[i]; j++) { // find team[i] of val team[i]
// cout<<"j: "<<j<<endl;
if (have.size() == 0) // run out
return 0;
ii minv = *(have.begin()); // lowest end, greedy
// cout<<"minv: "<<minv.fi<<", "<<minv.se<<endl;
have.erase(have.find(minv));
tr1[minv.se].erase(tr1[minv.se].find(minv.fi));
tr2[minv.fi].erase(tr2[minv.fi].find(minv.se));
}
}
return 1;
}
