#include "teams.h"
//#include "grader.cpp"
#include <set>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 5e5 + 5;
struct SegmentTree
{
int val;
SegmentTree *L, *R;
SegmentTree()
{
this->val = 0;
this->L = nullptr;
this->R = nullptr;
}
void copyFrom(SegmentTree *other)
{
val = other->val;
}
void build(int l, int r)
{
if(l==r) return;
L = new SegmentTree();
R = new SegmentTree();
L->build(l, (l+r)/2);
R->build((l+r)/2+1, r);
}
int query(int ql, int qr, int l, int r)
{
if(l>=ql && r<=qr) return val;
if(r<ql || l>qr) return 0;
return L->query(ql, qr, l, (l+r)/2) + R->query(ql, qr, (l+r)/2+1, r);
}
void update(int q, int change, SegmentTree *other, int l, int r)
{
copyFrom(other);
//cout << l << " " << r << " -> " << q << '\n';
if(l==r && l==q)
{
val += change;
return;
}
if(l<=q && q<=(l+r)/2)
{
L = new SegmentTree();
L->update(q, change, other->L, l, (l+r)/2);
}
else
{
L = other->L;
}
if((l+r)/2+1<=q && q<=r)
{
R = new SegmentTree();
R->update(q, change, other->R, (l+r)/2+1, r);
}
else
{
R = other->R;
}
val = L->val + R->val;
}
};
struct Event
{
int type;
int pos;
pair <int, int> info;
Event(){}
Event(int type, int pos, pair <int, int> info)
{
this->type = type;
this->pos = pos;
this->info = info;
}
};
bool operator <(Event A, Event B)
{
if(A.pos!=B.pos) return A.pos<B.pos;
return A.type<B.type;
}
int n;
int *a, *b;
long long dp[MAXN];
SegmentTree *T[MAXN];
vector <int> start2End[MAXN];
SegmentTree* createTree()
{
return new SegmentTree();
}
int getInside(int x1, int x2, int y1, int y2)
{
if(x1>x2 || y1>y2) return 0;
int ans = T[x2]->query(y1, y2, 1, n);
if(x1!=0) ans -= T[x1-1]->query(y1, y2, 1, n);
return ans;
}
void init(int N, int A[], int B[])
{
n = N;
a = A;
b = B;
for(int i = 0;i<n;i++)
start2End[ a[i] ].push_back(b[i]);
T[0] = createTree();
T[0]->build(1, n);
for(int i = 1;i<=n;i++)
{
T[i] = T[i-1];
for(int x: start2End[i])
{
SegmentTree *buff = createTree();
buff->update(x, +1, T[i], 1, n);
T[i] = buff;
}
}
/*
while(true)
{
int x1, x2, y1, y2;
cin >> x1 >> x2 >> y1 >> y2;
cout << getInside(x1, x2, y1, y2) << '\n';
}
*/
}
int slowSolve(int M, int K[])
{
multiset <pair <int, int>> s;
vector <Event> v;
for(int i = 0;i<n;i++)
{
v.push_back(Event(0, a[i], {b[i], a[i]}));
v.push_back(Event(2, b[i], {b[i], a[i]}));
}
for(int i = 0;i<M;i++)
{
v.push_back(Event(1, K[i], {K[i], K[i]}));
}
sort(v.begin(), v.end());
//for(Event e: v) cout << e.type << " -> " << e.info.first << " " << e.info.second << '\n';
for(Event e: v)
{
if(e.type==0)
{
s.insert(e.info);
}
else if(e.type==1)
{
if(s.size()<e.info.first) return 0;
for(int rem = 0;rem<e.info.first;rem++) s.erase(s.find(*s.begin()));
}
else if(e.type==2)
{
if(s.find(e.info)!=s.end()) s.erase(s.find(e.info));
}
//cout << e.type << " -> " << e.info.first << " " << e.info.second << " || " << s.size() << '\n';
}
return 1;
}
long long eval(int i, int j, int K[])
{
return dp[j] + getInside(K[j]+1, K[i], K[i], n) - K[i];
}
bool quickCheck(int M, int K[])
{
int sum = 0;
for(int i = 0;i<M;i++)
{
sum += K[i];
if(sum>n) return true;
}
return false;
}
int can(int M, int K[])
{
//if(M>sqrt(n)) return slowSolve(M, K);
if(quickCheck(M, K)==true) return 0;
sort(K, K+M);
for(int i = 0;i<=M;i++) dp[i] = 0;
vector <int> inds;
for(int i = 0;i<M;i++)
{
dp[i] = getInside(1, K[i], K[i], n) - K[i];
while(inds.size()>=2 && eval(i, inds[inds.size()-2], K)<=eval(i, inds[inds.size()-1], K)) inds.pop_back();
for(int j = inds.size()-1;j>=max(0, int(inds.size())-5);j--)
dp[i] = min(dp[i], eval(i, inds[j], K));
inds.push_back(i);
}
long long minVal = MAXN;
for(int i = 0;i<M;i++) minVal = min(minVal, dp[i]);
if(minVal<0) return 0;
return 1;
}
/*
4
1 2
2 3
2 3
2 4
2
2
1 3
2
1 1
*/
