1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 #define N 80001 6 int sum,sz,num[N],l[295],r[295],a[N],op[N],en,ma[N],ans,n; 7 inline void R(int &x){ 8     char c=0;int f=1; 9     for(;c<‘0‘||c>‘9‘;c=getchar())if(c==‘-‘)f=-1;10     for(x=0;c>=‘0‘&&c<=‘9‘;c=getchar())(x*=10)+=(c-‘0‘);11     x*=f;12 }13 void makeblock()14 {15     sz=sqrt(en); if(!sz) sz=1;16     for(sum=1;sum*sz<en;sum++)17       {18         l[sum]=r[sum-1]+1;19         r[sum]=sum*sz;20         for(int i=l[sum];i<=r[sum];i++) num[i]=sum;21       }22     l[sum]=r[sum-1]+1;23     r[sum]=en;24     for(int i=l[sum];i<=r[sum];i++) num[i]=sum;25 }26 struct Val_Blocks27 {28     int sumv[295],Size;29     bool b[N];30     inline void Insert(const int &x){b[x]=1; sumv[num[x]]++; Size++;}31     inline void Delete(const int &x){b[x]=0; sumv[num[x]]--; Size--;}32     inline int Next(const int &x)33       {34         if(b[x]) return x;35         for(int i=x+1;i<=r[num[x]];i++) if(b[i]) return i;36         for(int i=num[x]+1;i<=sum;i++) if(sumv[i])37           for(int j=l[i];;j++)38             if(b[j]) return j;39         return -1;40       }41     inline int Pre(const int &x)42       {43         if(b[x]) return x;44         for(int i=x-1;i>=l[num[x]];i--) if(b[i]) return i;45         for(int i=num[x]-1;i>=1;i--) if(sumv[i])46           for(int j=r[i];;j--)47             if(b[j]) return j;48         return -1;49       }50 }T[2];51 struct Point{int v,p;}t[N];52 bool operator < (const Point &a,const Point &b){return a.v<b.v;}53 int main()54 {55     R(n); for(int i=1;i<=n;i++)56       {57           R(op[i]); R(t[i].v);58           t[i].p=i;59       } sort(t+1,t+n+1);60     ma[a[t[1].p]=++en]=t[1].v;61     for(int i=2;i<=n;i++)62       {63           if(t[i].v!=t[i-1].v) en++;64           ma[a[t[i].p]=en]=t[i].v;65       } makeblock();66     for(int i=1;i<=n;i++)67       {68           if(!T[op[i]^1].Size) T[op[i]].Insert(a[i]);69           else70             {71                 int Up=T[op[i]^1].Next(a[i]),Down=T[op[i]^1].Pre(a[i]);72                 if(Up==-1||(Down!=-1&&ma[a[i]]-ma[Down]<=ma[Up]-ma[a[i]]))73                   {74                       ans=(ans+ma[a[i]]-ma[Down])%1000000;75                       T[op[i]^1].Delete(Down);76                   }77                 else78                   {79                       ans=(ans+ma[Up]-ma[a[i]])%1000000;80                       T[op[i]^1].Delete(Up);81                   }82             }83       } printf("%d\n",ans);84     return 0;85 }