#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
struct data{
int s, e;
bool operator < (const data &r) const {
if(e == r.e) return s < r.s;
return e < r.e;
}
} a[500100];
struct Node {
int gap;
Node *lf, *rg;
Node() {
gap = 0; lf = rg = NULL;
}
} *tree[500100];
Node* add(Node* now, int s, int e, int target, int v) {
if(now == NULL) { now = new Node(); }
if(s > target || e < target) return now;
if(s == e) { Node *ret = new Node(); ret->gap = now->gap + 1; return ret; }
int m = s+e>>1;
Node* ret = new Node();
Node* lch = add(now->lf, s, m, target, v);
Node* rch = add(now->rg, m+1, e, target, v);
ret->gap = lch->gap + rch->gap; ret->lf = lch; ret->rg = rch;
return ret;
}
int query(Node* now, int s, int e, int si, int ei){
if(now == NULL) return 0;
if(s > ei || e < si) return 0;
if(s >= si && e <= ei) return now->gap;
int m = s+e>>1;
return query(now->lf, s, m, si, ei) + query(now->rg, m+1, e, si, ei);
}
int p[500100], q[500100], num[500100], K[500100], ptr[500100], N;
int Cnt[801][801], qQ[500100];
int Count(int xs, int xe, int ys, int ye) {
return query(tree[xe], 1, N, ys, ye) - query(tree[xs-1], 1, N, ys, ye);
}
void init(int _N, int A[], int B[]) {
N = _N;
int i;
for(i=1; i<=N; i++) a[i].s = A[i-1], a[i].e = B[i-1];
sort(a+1, a+N+1);
for(i=1; i<=N; i++) p[i] = a[i].s, q[i] = a[i].e;
tree[0] = new Node();
for(i=1; i<=N; i++) {
tree[i] = new Node();
tree[i]->gap = tree[i-1]->gap; tree[i]->lf = tree[i-1]->lf; tree[i]->rg = tree[i-1]->rg;
tree[i] = add(tree[i], 1, N, p[i], 1);
}
for(i=1; i<=N; i++) qQ[i] = lower_bound(q+1, q+N+1, i) - q;
}
int can(int M, int k[]) {
int i, j;
for(i=1; i<=M; i++) K[i] = k[i-1];
sort(K+1, K+M+1);
for(i=1; i<=M; i++) num[K[i]] = 0;
for(i=1; i<=M; i++) num[K[i]] += K[i];
M = unique(K+1, K+M+1) - K - 1;
int now = 0, ans = 1;
for(i=1; i<=M; i++) {
int numHap = 0;
ptr[i] = qQ[K[i]];
for(j=1; j<i; j++) {
if(num[K[j]] == 0) continue;
int numCnt = Count(ptr[i-1], ptr[i]-1, 1, K[j]) - numHap;
now -= min(numCnt, num[K[j]]);
numHap += min(numCnt, num[K[j]]);
num[K[j]] -= min(numCnt, num[K[j]]);
}
now += num[K[i]];
int cnt = Count(ptr[i], N, 1, K[i]);
if(cnt < now) ans = 0;
}
return ans;
}
