首页 > 代码库 > 【set】【Splay】【pb_ds】bzoj1208 [HNOI2004]宠物收养所
【set】【Splay】【pb_ds】bzoj1208 [HNOI2004]宠物收养所
每次来的如果是人，且宠物数不为零，就从宠物中选出一个与其差距最小的，累加答案；若为零，就把他放入另一个集合里。
如果是宠物，则同上。
各种平衡树都可过，我蛋疼地用了pb_ds。
Code:
1 #include<cstdio> 2 #include<ext/pb_ds/assoc_container.hpp> 3 #include<ext/pb_ds/tree_policy.hpp> 4 using namespace std; 5 using namespace __gnu_cxx; 6 using namespace __gnu_pbds; 7 tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> T[2]; 8 typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>::iterator ITER; 9 int n,op,a,ans;10 inline bool empty(const int &x){return T[x].lower_bound(-2147483647)==T[x].end() ? true : false;}11 inline int Abs(const int &x){return x<0 ? (-x) : x;}12 int main()13 {14 scanf("%d",&n);15 for(int i=1;i<=n;i++)16 {17 scanf("%d%d",&op,&a);18 if(empty(op^1))19 T[op].insert(a);20 else21 {22 ITER it=T[op^1].lower_bound(a);23 if((*it)==a)24 T[op^1].erase(it);25 else26 {27 ITER it2=T[op^1].upper_bound(a);28 if(it==T[op^1].begin())29 {30 ans=(ans+Abs(a-(*it2)))%1000000;31 T[op^1].erase(it2);32 continue;33 }34 it--;35 if(it2==T[op^1].end())36 {37 ans=(ans+Abs(a-(*it)))%1000000;38 T[op^1].erase(it);39 continue;40 }41 if(Abs(a-(*it2))<Abs(a-(*it)))42 {43 ans=(ans+Abs(a-(*it2)))%1000000;44 T[op^1].erase(it2);45 continue;46 }47 else48 {49 ans=(ans+Abs(a-(*it)))%1000000;50 T[op^1].erase(it);51 }52 }53 }54 }55 printf("%d\n",ans);56 return 0;57 }
【set】【Splay】【pb_ds】bzoj1208 [HNOI2004]宠物收养所
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。