题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1208
看网上的题解都用的手写数据结构……然而直接用set的lower_bound就水过去了……
#include<bits/stdc++.h>
using namespace std; const int md=;
set<int> pet,people; int main()
{
int n;
scanf("%d",&n);
int ans=;
while (n--)
{
int op,x;
scanf("%d%d",&op,&x);
if (op==)
{
if (people.empty())
{
pet.insert(x);
}
else
{
set<int>::iterator it = people.lower_bound(x);
if (it==people.begin())
{
ans=(ans+abs(*it-x))%md;
}
else if (it==people.end())
{
--it;
ans=(ans+abs(*it-x))%md;
}
else
{
set<int>::iterator it2=--it;
++it;
if (abs(*it2-x)<=abs(*it-x)) --it;
ans=(ans+abs(*it-x))%md;
}
people.erase(it);
}
}
else
{
if (pet.empty())
{
people.insert(x);
}
else
{
set<int>::iterator it = pet.lower_bound(x);
if (it==pet.begin())
{
ans=(ans+abs(*it-x))%md;
}
else if (it==pet.end())
{
--it;
ans=(ans+abs(*it-x))%md;
}
else
{
set<int>::iterator it2=--it;
++it;
if (abs(*it2-x)<=abs(*it-x)) --it;
ans=(ans+abs(*it-x))%md;
}
pet.erase(it);
}
}
}
printf("%d\n",ans);
return ;
}