Description
与很多奶牛一样，Farmer John那群养尊处优的奶牛们对食物越来越挑剔，随便拿堆草就能打发她们午饭的日子自然是一去不返了。现在，Farmer John不得不去牧草专供商那里购买大量美味多汁的牧草，来满足他那N(1 <= N <= 100,000)头挑剔的奶牛。 所有奶牛都对FJ提出了她对牧草的要求：第i头奶牛要求她的食物每份的价钱不低于A_i(1 <= A_i <= 1,000,000,000)，并且鲜嫩程度不能低于B_i(1 <= B_i <= 1,000,000,000)。商店里供应M(1 <= M <= 100,000)种不同的牧草，第i 种牧草的定价为C_i(1 <= C_i <= 1,000,000,000)，鲜嫩程度为D_i (1 <= D_i <= 1,000,000,000)。 为了显示她们的与众不同，每头奶牛都要求她的食物是独一无二的，也就是说，没有哪两头奶牛会选择同一种食物。 Farmer John想知道，为了让所有奶牛满意，他最少得在购买食物上花多少钱。
Input
* 第1行: 2个用空格隔开的整数：N 和 M
* 第2..N+1行: 第i+1行包含2个用空格隔开的整数：A_i、B_i * 第N+2..N+M+1行: 第j+N+1行包含2个用空格隔开的整数：C_i、D_i
Output
* 第1行: 输出1个整数，表示使所有奶牛满意的最小花费。如果无论如何都无法 满足所有奶牛的需求，输出-1
思路：
贪心+treap查找后继
假设有一个牧草满足某一个奶牛的要求，根据贪心的思想，一定是价钱和鲜嫩程度都最贴近奶牛的要求的，现在的问题是有两种元素我们需要比较，所以我们就需要提前处理好一种元素，用treap去维护另一种元素：先将牧草按鲜嫩程度，奶牛按鲜嫩程度要求从大到小排序，枚举每一个奶牛的要求，首先将所有那些鲜嫩程度大于等于当前奶牛要求的牧草加入到treap里 ，然后求出treap中所有牧草价钱 (第一个大于等于)奶牛要求的价钱，也就是求一个数的后继 再删去这个牧草就可以了 最后，不要忘记判断输出‘-1’的情况
#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;
struct your
{
int l,r,v,rnd,w;
}a[200000];
int root,tot,aftr;
void lturn(int &k)
{
int t=a[k].r;
a[k].r=a[t].l;
a[t].l=k,k=t;
}
void rturn(int &k)
{
int t=a[k].l;
a[k].l=a[t].r;
a[t].r=k,k=t;
}
void update(int &k,int temp)
{
if(!k)
{
k=++tot;
a[k].w=1;
a[k].v=temp;
a[k].rnd=rand();
return ;
}
if(temp==a[k].v) a[k].w++;
else if(temp<a[k].v)
{
update(a[k].l,temp);
if(a[a[k].l].rnd<a[k].rnd) rturn(k);
}
else
{
update(a[k].r,temp);
if(a[a[k].r].rnd<a[k].rnd) lturn(k);
}
}
void del(int &k,int temp)
{
if(temp==a[k].v)
{
if(a[k].w>1)a[k].w--;
else if(a[k].l*a[k].r==0)
k=a[k].l+a[k].r;
else if(a[a[k].l].rnd<a[a[k].r].rnd)
rturn(k),del(k,temp);
else lturn(k),del(k,temp);
}
else if(temp<a[k].v) del(a[k].l,temp);
else del(a[k].r,temp);
}
void ask_after(int k,int temp)
{
if(!k) return ;
if(temp<=a[k].v)
{
aftr=a[k].v;
ask_after(a[k].l,temp);
}
else ask_after(a[k].r,temp);
}
int n,m;
struct FJ
{
int x,y;
}cow[110000],grass[110000];
bool cmp(FJ j,FJ k)
{
return j.y>k.y;
}
long long ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&cow[i].x,&cow[i].y);
for(int i=1;i<=m;i++)
scanf("%d%d",&grass[i].x,&grass[i].y);
sort(cow+1,cow+n+1,cmp);
sort(grass+1,grass+m+1,cmp);
int cnt=1;
for(int i=1;i<=n;i++)
{
aftr=-1;
while(cnt<=m&&grass[cnt].y>=cow[i].y)
{
update(root,grass[cnt].x);
cnt++;
}
ask_after(root,cow[i].x);
if(aftr==-1)
{
printf("-1\n");
return 0;
}
ans+=aftr,del(root,aftr);
}
printf("%lld",ans);
}