HDU/HDOJ----4302 Holedox Eating

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
#include <iostream>
#include <cstdio>
#include <cmath>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1^1
#define ll long long
#define N 100005
#define inf 1e9
#define linf 1e9
#define rinf -1
using namespace std;
struct node{
int left,right;
int num,lmost,rmost;
}seg[3*N];
int min(int a,int b) { return a<b?a:b; }
int max(int a,int b) { return a>b?a:b; }
void segtree_build(int l,int r,int rt){
//cout<<"<"<<l<<","<<r<<">"<<endl;
seg[rt].left=l,seg[rt].right=r;
seg[rt].num=0,seg[rt].lmost=linf,seg[rt].rmost=rinf;
if(l==r) return ;
int mid=(l+r)>>1;
segtree_build(lson);
segtree_build(rson);
}
node segtree_query(int L,int R,int l,int r,int rt){
node ans,tl,tr;
ans.lmost=linf,ans.rmost=rinf;
if(L<=l&&r<=R){
ans.lmost=min(ans.lmost,seg[rt].lmost);
ans.rmost=max(ans.rmost,seg[rt].rmost);
return ans;
}
int mid=(seg[rt].left+seg[rt].right)>>1;
if(L<=mid){
tl=segtree_query(L,R,lson);
ans.lmost=min(ans.lmost,tl.lmost);
ans.rmost=max(ans.rmost,tl.rmost);
}
if(R>mid){
tr=segtree_query(L,R,rson);
ans.lmost=min(ans.lmost,tr.lmost);
ans.rmost=max(ans.rmost,tr.rmost);
}
return ans;
}
void segtree_insert(int p,int rt,int index){
seg[rt].num+=index;
if(seg[rt].num==0) seg[rt].lmost=linf,seg[rt].rmost=rinf;
if(seg[rt].left==p&&seg[rt].right==p){
if(seg[rt].num) seg[rt].lmost=p,seg[rt].rmost=p;
return ;
}
int mid=(seg[rt].left+seg[rt].right)>>1;
if(p<=mid) segtree_insert(p,rt<<1,index);
else segtree_insert(p,rt<<1^1,index);
if(seg[rt].num){
seg[rt].lmost=min(seg[rt<<1].lmost,seg[rt<<1^1].lmost);
seg[rt].rmost=max(seg[rt<<1].rmost,seg[rt<<1^1].rmost);
}
}
void segtree_print(int L){
for(int i=1;i<=L*2;i*=2){
for(int j=0;j<i;j++){
int pos=i+j;
printf("<%d,%d> ",seg[pos].left,seg[pos].right);
if(seg[pos].lmost==linf) printf("no ");
else printf("%d ",seg[pos].lmost);
if(seg[pos].rmost==rinf) printf("no ");
else printf("%d ",seg[pos].rmost);
printf("%d| ",seg[pos].num);
}
printf("n");
for(int k=0;k<80;k++)
printf("-");
printf("n");
}
}
int main(){
//freopen("in.in","r",stdin);
int T,L,n,Case=1;
int lp,rp,ld,rd;
scanf("%d",&T);
while(T--){
scanf("%d%d",&L,&n);
segtree_build(0,L,1);
//segtree_print(L);
//cout<<"segtree_build done!"<<endl;
int lst=0,pos=0,ope,p;
ll ans=0;
while(n--){
scanf("%d",&ope);
if(ope){
lp=segtree_query(0,pos,0,L,1).rmost; ld=(lp==rinf?inf:abs(lp-pos)); //if(lp==inf) cout<<"no"<<' '; else cout<<"lp="<<lp<<' ';
rp=segtree_query(pos,L,0,L,1).lmost; rd=(rp==linf?inf:abs(rp-pos)); //if(rp==inf) cout<<"no"<<endl; else cout<<"rp="<<rp<<endl;
if(ld==inf&&rd==inf) continue;
else if(ld<rd||(ld==rd&&lst==-1)){
pos=lp,lst=-1,ans+=(ll)ld;
segtree_insert(pos,1,-1);
//segtree_print(L);
//cout<<"delete "<<pos<<" done!"<<endl;
}
else if(ld>rd||(ld==rd&&lst==1)){
pos=rp,lst=1,ans+=(ll)rd;
segtree_insert(pos,1,-1);
//segtree_print(L);
//cout<<"delete "<<pos<<" done!"<<endl;
}
else if(ld==rd&&lst==0){
segtree_insert(pos,1,-1);
//segtree_print(L);
//cout<<"delete "<<pos<<" done!"<<endl;
}
//cout<<"pos="<<pos<<' '<<"lst="<<lst<<' '<<"ans="<<ans<<endl;
}
else{
scanf("%d",&p);
segtree_insert(p,1,1);
//segtree_print(L);
//cout<<"insert "<<p<<" done!"<<endl;
}
}
printf("Case %d: %lldn",Case++,ans);
}
return 0;
}