1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
#include <bits/stdc++.h>
#define MAXN 500005
#define MOD 1000000
using namespace std;
inline int read() {
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9') {
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9') {
x=(x*10)+(ch-'0');
ch=getchar();
}
return x*f;
}
namespace FHQ_Treap{
struct node{
int l,r;
int val;
int pri;
int sz;
}tree[MAXN];
int tot;
#define lc(i) tree[i].l
#define rc(i) tree[i].r
inline void Update(int x){
tree[x].sz=tree[lc(x)].sz+tree[rc(x)].sz+1;
}
inline int New(int v){
tree[++tot].val=v;
tree[tot].pri=rand();
tree[tot].sz=1;
return tot;
}
int Merge(int x,int y){
if (!x||!y) return x+y;
if (tree[x].pri<tree[y].pri){
rc(x)=Merge(rc(x),y),Update(x);
return x;
}
else {
lc(y)=Merge(x,lc(y)),Update(y);
return y;
}
}
void Split(int i,int k,int &x,int &y){
if (!i){
x=y=0;
}
else {
if (tree[i].val<=k){x=i,Split(rc(i),k,rc(i),y);}
else{y=i,Split(lc(i),k,x,lc(i));}
Update(i);
}
}
int kth(int i,int k){
while (true){
if (k<=tree[lc(i)].sz){
i=lc(i);
}
else if (k==tree[lc(i)].sz+1){
return i;
}
else{
k-=tree[lc(i)].sz+1;
i=rc(i);
}
}
}
int root,x,y,z;
void Init(){
tot=0;
memset(tree,0,sizeof(tree));
root=0;
srand(19260817);
}
inline void Add(int num){
Split(root,num,x,y);
root=Merge(Merge(x,New(num)),y);
}
inline void Del(int num){
Split(root,num,x,z);
Split(x,num-1,x,y);
y=Merge(lc(y),rc(y));
root=Merge(Merge(x,y),z);
}
inline int Rank(int num){
Split(root,num-1,x,y);
int temp=tree[x].sz+1;
root=Merge(x,y);
return temp;
}
#define Get_K(rt,rk) tree[kth(rt,rk)].val
inline int Kth(int k){
return Get_K(root,k);
}
inline int Pre(int num){
Split(root,num-1,x,y);
int temp=Get_K(x,tree[x].sz);
root=Merge(x,y);
return temp;
}
inline int Nex(int num){
Split(root,num,x,y);
int temp=Get_K(y,1);
root=Merge(x,y);
return temp;
}
};
using namespace FHQ_Treap;
#define INF 0x3f3f3f3f
inline int Abs(int x){
return x>0?x:-x;
}
int main(){
Init();
int n=read();
Add(INF),Add(-INF);
int pets=0;
int man=0;
int ans=0;
for (register int i=1;i<=n;++i){
int opr=read(),p=read();
if (pets==man){
Add(p);
}
else{
if ((opr==0&&pets>man)||(opr==1&&pets<man)){
Add(p);
}
else {
int pre=Pre(p),nex=Nex(p);
int d1=p-pre,d2=nex-p;
if (d1<=d2) ans+=d1,Del(pre);
else ans+=d2,Del(nex);
}
}
if (opr==0) pets++;
else man++;
ans%=MOD;
}
printf("%d\n",ans);
}
|
