#include "teams.h"
#include<bits/stdc++.h>
#define MAX 500500
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using namespace std;
class SegmentTree {
private:
struct Node {
int cnt;
Node *left,*right;
Node() {
cnt=0;
left=right=NULL;
}
Node(Node *p) {
cnt=p->cnt;
left=p->left;
right=p->right;
}
};
Node *root;
int n;
int get(Node *p,int l,int r,int u,int v) const {
if (l>v || r<u || l>r || v<u) return (0);
if (u<=l && r<=v) return (p->cnt);
int m=(l+r)>>1;
int L=get(p->left,l,m,u,v);
int R=get(p->right,m+1,r,u,v);
return (L+R);
}
void build(Node *&p,int l,int r) {
if (l>r) return;
p=new Node();
if (l==r) return;
int m=(l+r)>>1;
build(p->left,l,m);
build(p->right,m+1,r);
}
public:
SegmentTree() {
n=0;
root=NULL;
}
SegmentTree(int n) {
this->n=n;
build(root,1,n);
}
void update(int x) {
assert(1<=x && x<=n);
root=new Node(root);
Node *p=root;
int l=1;
int r=n;
while (true) {
p->cnt++;
if (l==r) return;
int m=(l+r)>>1;
if (x>m) {
l=m+1;
p->right=new Node(p->right);
p=p->right;
} else {
r=m;
p->left=new Node(p->left);
p=p->left;
}
}
}
int get(int l,int r) const {
assert(1<=l && r<=n);
return (get(root,1,n,l,r));
}
};
int n,cntTime;
pair<int,int> a[MAX];
SegmentTree myit[MAX+7];
int randint(int l,int r) {
assert(l<=r);
return (l+rand()%(r-l+1));
}
void init(int N, int A[], int B[]) {
n=N;
REP(i,n) {
/*int L=randint(1,n);
int R=randint(1,n);
if (L>R) swap(L,R);*/
a[i+1]=make_pair(A[i],B[i]);
}
sort(a+1,a+n+1);
myit[0]=SegmentTree(MAX);
int id=1;
FOR(i,1,MAX) {
myit[i]=myit[i-1];
while (id<=n && a[id].fi<=i) {
myit[i].update(a[id].se);
id++;
}
}
/*srand(time(NULL));
int a=0;
REP(love,1000000) {
int L=randint(1,MAX);
int minR=randint(1,MAX);
int maxR=randint(1,MAX);
if (minR>maxR) swap(minR,maxR);
//cerr<<L<<" "<<minR<<" "<<maxR<<endl;
a^=myit[L].get(minR,maxR);
}
cerr<<a<<endl;
fprintf(stderr,"Done\n");*/
}
int countPair(int l,int minR,int maxR) {
if (l<1) return (0);
if (minR<1) minR=1;
if (maxR>MAX) maxR=MAX;
if (minR>maxR) return (0);
/*int res=0;
FOR(i,1,n) if (a[i].fi<=l && minR<=a[i].se && a[i].se<=maxR) res++;
return (res);*/
return (myit[l].get(minR,maxR));
}
int countPair(int minL,int maxL,int minR,int maxR) {
if (minL>maxL || minR>maxR) return (0);
return (countPair(maxL,minR,maxR)-countPair(minL-1,minR,maxR));
}
int can(int M, int K[]) {
long long sum=0;
REP(i,M) sum+=K[i];
if (sum>n) return (0);
map<int,int> mp;
REP(i,M) mp[K[i]]+=K[i];
vector<pair<int,int> > v(ALL(mp));
int prevUsed=0;
REP(i,v.size()) {
int cur=v[i].fi;
int req=v[i].se;
fprintf(stderr,"At value %d req %d\n",cur,req);
int next=i+1<(int)v.size()?v[i+1].fi:MAX;
int prev=i>0?v[i-1].fi:-1;
int oldSmall=countPair(1,prev,cur,next-1);
int oldBig=countPair(1,prev,next,MAX);
int newSmall=countPair(prev+1,cur,cur,next-1);
int newBig=countPair(prev+1,cur,next,MAX);
fprintf(stderr,"old: %d | %d\n",oldSmall,oldBig);
fprintf(stderr,"new: %d | %d\n",newSmall,newBig);
assert(oldSmall+oldBig>=prevUsed);
if (oldSmall<prevUsed) {
oldBig-=prevUsed-oldSmall;
prevUsed-=oldSmall;
oldSmall=0;
} else {
oldSmall-=prevUsed;
prevUsed=0;
}
int numSmall=oldSmall+newSmall;
int numBig=oldBig+newBig;
if (numSmall+numBig<req) return (0);
prevUsed+=numSmall<req?req-numSmall:0;
fprintf(stderr,"prevUsed %d\n",prevUsed);
}
return (1);
}
