1 #include<bits/stdc++.h> 2 #define cl(a,b) memset(a,b,sizeof(a)) 3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl 4 using namespace std; 5  6 const int maxn=15000+10; 7 const int mod=1000000; 8  9 multiset<int>a[2];10 11 int main()12 {13     int n;14     while(~scanf("%d",&n))15     {16         a[0].clear(),a[1].clear();17         int last=-1,ans=0;18         int x,y;19         for(int i=0; i<n; i++)20         {21             scanf("%d%d",&x,&y);22             if(a[0].empty()&&a[1].empty())23             {24                 last=x;25                 a[x].insert(y);26             }27             else if(x==last&&a[!last].empty())28             {29                 a[last].insert(y);30             }31             else32             {33                 auto set_iter=a[last].lower_bound(y);34                 if(*a[last].rbegin()<y)35                 {36                     //set_iter=a[last].rbegin();37                     //上面这句话是不对的 因为反向迭代器不能给普通迭代器赋值38                     //所以要用base()方法获取相应的迭代器再赋值39                     set_iter=a[last].rbegin().base();40                 }41                 int mi=abs(*set_iter-y);42                 if(set_iter!=a[last].begin())43                 {44                     set_iter--;45                 }46                 if(mi>=abs(*set_iter-y))47                 {48                     a[last].erase(set_iter);49                     ans+=abs(*set_iter-y);50                     ans%=mod;51                 }52                 else53                 {54                     set_iter++;55                     a[last].erase(set_iter);56                     ans+=mi;57                     ans%=mod;58                 }59             }60         }61         printf("%d\n",ans);62     }63     return 0;64 }65 66 /*67 68 569 0 270 0 471 1 372 1 273 1 574 75 */