CodeFoces 500E - New Year Domino

98 阅读 0 评论 65 点赞

我是靠谱客的博主陶醉枕头，这篇文章主要介绍CodeFoces 500E - New Year Domino，现在分享给大家，希望可以做个参考。

首先将所有的牌子放倒，那么花费就是牌子L和牌子R之间的空隙长度。

有一种特殊情况，存在牌子P(p < L)特别长，以至于影响了L，R之间的空隙长度。

所以我只想到了一种离线算法。

cov[i] 记录覆盖牌子i的编号。

dis[i] 记录推到牌子i所能到达的最远距离。

cost[i]记录L= i，R = n 时的最小花费。

首先预处理出dis[i],cost[i]。

然后将询问按L排序，然后从右到左枚举牌子。

枚举时不断更新cov[i]，然后分类讨论得到答案。

弱用了三棵线段树才水过去，应该存在更简洁的方法。

复制代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <ctime>
#include <iomanip>
#pragma comment(linker,"/STACK:1024000000");
#define EPS (1e-6)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define mod 1000000007
/** I/O Accelerator Interface .. **/
#define g (c=getchar())
#define d isdigit(g)
#define p x=x*10+c-'0'
#define n x=x*10+'0'-c
#define pp l/=10,p
#define nn l/=10,n
template<class T> inline T& RD(T &x)
{
char c;
while(!d);
x=c-'0';
while(d)p;
return x;
}
template<class T> inline T& RDD(T &x)
{
char c;
while(g,c!='-'&&!isdigit(c));
if (c=='-')
{
x='0'-g;
while(d)n;
}
else
{
x=c-'0';
while(d)p;
}
return x;
}
inline double& RF(double &x)
//scanf("%lf", &x);
{
char c;
while(g,c!='-'&&c!='.'&&!isdigit(c));
if(c=='-')if(g=='.')
{
x=0;
double l=1;
while(d)nn;
x*=l;
}
else
{
x='0'-c;
while(d)n;
if(c=='.')
{
double l=1;
while(d)nn;
x*=l;
}
}
else if(c=='.')
{
x=0;
double l=1;
while(d)pp;
x*=l;
}
else
{
x=c-'0';
while(d)p;
if(c=='.')
{
double l=1;
while(d)pp;
x*=l;
}
}
return x;
}
#undef nn
#undef pp
#undef n
#undef p
#undef d
#undef g
using namespace std;
struct N
{
int l,p;
}st[200010];
int far[200010];
int Max[800100];
int dis[200010];
int Val[800100];
LL cost[200100];
int Init(int site,int l,int r)
{
if(l == r)
return Val[site] = st[l].l+st[l].p;
int mid = (l+r)>>1;
return Val[site] = max(Init(site<<1,l,mid),Init(site<<1|1,mid+1,r));
}
void Update(int site,int l,int r,int x,int d)
{
if(l == r)
{
Max[site] = max(Max[site],d);
return ;
}
int mid = (l+r)>>1;
if(x <= mid)
Update(site<<1,l,mid,x,d);
else
Update(site<<1|1,mid+1,r,x,d);
Max[site] = max(Max[site<<1],Max[site<<1|1]);
}
int Query(int site,int L,int R,int l,int r)
{
if(L == l && R == r)
return Max[site];
int mid = (L+R)>>1;
if(r <= mid)
return Query(site<<1,L,mid,l,r);
if(mid < l)
return Query(site<<1|1,mid+1,R,l,r);
return max(Query(site<<1,L,mid,l,mid),Query(site<<1|1,mid+1,R,mid+1,r));
}
int Query1(int site,int L,int R,int l,int r)
{
if(L == l && R == r)
return Val[site];
int mid = (L+R)>>1;
if(r <= mid)
return Query1(site<<1,L,mid,l,r);
if(mid < l)
return Query1(site<<1|1,mid+1,R,l,r);
return max(Query1(site<<1,L,mid,l,mid),Query1(site<<1|1,mid+1,R,mid+1,r));
}
int BS(LL x,int s,int e)
{
int mid , site = 0;
while(s <= e)
{
mid = (s+e)>>1;
if(st[mid].p <= x)
s = mid+1,site = mid;
else
e = mid-1;
}
return site;
}
void Cal(int x,int n)
{
int site = BS(st[x].l+st[x].p,x,n);
if(site == x)
far[x] = x;
else if(site == n)
far[x] = n;
else
far[x] = Query(1,1,n,x,site);
Update(1,1,n,x,far[x]);
}
int FindSite(int x,int l,int r)
{
int mid,site = r;
while(l <= r)
{
mid = (l+r)>>1;
if(far[mid] == x)
site = min(site,mid);
if(far[mid] < x)
l = mid+1;
else
r = mid-1;
}
return site;
}
struct Qu
{
int l,r,site;
LL anw;
}qu[200010];
bool cmp1(Qu q1,Qu q2)
{
return q1.l < q2.l;
}
bool cmp2(Qu q1,Qu q2)
{
return q1.site < q2.site;
}
struct Co
{
int id;
bool mark;
}cov[800100];
void InitCo(int site,int l,int r)
{
if(l == r)
{
cov[site].id = l,cov[site].mark = true;
return ;
}
int mid =(l+r)>>1;
InitCo(site<<1,l,mid);
InitCo(site<<1|1,mid+1,r);
if(cov[site<<1].id == cov[site<<1|1].id && cov[site<<1].id != -1)
cov[site].mark = true,cov[site].id = cov[site<<1].id;
else
cov[site].mark = false,cov[site].id = -1;
}
void UpdateCo(int site,int L,int R,int l,int r,int id)
{
if(L == l && R == r)
{
cov[site].mark = true;
cov[site].id = id;
return ;
}
int mid = (L+R)>>1;
if(cov[site].mark == true)
{
cov[site<<1] = cov[site];
cov[site<<1|1] = cov[site];
cov[site].mark = false;
cov[site].id = -1;
}
if(r <= mid)
UpdateCo(site<<1,L,mid,l,r,id);
else if(mid < l)
UpdateCo(site<<1|1,mid+1,R,l,r,id);
else
{
UpdateCo(site<<1,L,mid,l,mid,id);
UpdateCo(site<<1|1,mid+1,R,mid+1,r,id);
}
if(cov[site<<1].id == cov[site<<1|1].id && cov[site<<1].id != -1)
cov[site].mark = true,cov[site].id = cov[site<<1].id;
else
cov[site].mark = false,cov[site].id = -1;
}
int QueryCo(int site,int L,int R,int x)
{
if(cov[site].mark )
return cov[site].id;
int mid = (L+R)>>1;
if(x <= mid)
return QueryCo(site<<1,L,mid,x);
else
return QueryCo(site<<1|1,mid+1,R,x);
}
int main()
{
int n,i,j,q;
scanf("%d",&n);
for(i = 1;i <= n; ++i)
scanf("%d %d",&st[i].p,&st[i].l);
memset(Max,0,sizeof(Max));
Update(1,1,n,n,n);
for(far[n] = n,i = n-1; i >= 1; --i)
Cal(i,n);
Init(1,1,n);
for(i = 1;i <= n; ++i)
dis[i] = Query1(1,1,n,i,far[i]);
for(cost[n] = 0,i = n-1;i >= 1; --i)
{
if(far[i] == n)
cost[i] = 0;
else
cost[i] = cost[far[i]+1] + st[far[i]+1].p - dis[i];
}
scanf("%d",&q);
int site;
for(i = 1;i <= q; ++i)
{
scanf("%d %d",&qu[i].l,&qu[i].r);
qu[i].site = i;
}
sort(qu+1,qu+q+1,cmp1);
InitCo(1,1,n);
for(j = q,i = n;i >= 1; --i)
{
UpdateCo(1,1,n,i,far[i],i);
while(j >= 1 && qu[j].l == i)
{
if(far[i] >= qu[j].r)
qu[j].anw = 0;
else
{
site = QueryCo(1,1,n,qu[j].r);
if(far[i] >= site)
qu[j].anw = 0;
else
qu[j].anw = cost[i] - cost[site];
}
j--;
}
}
sort(qu+1,qu+q+1,cmp2);
for(i = 1;i <= q; ++i)
{
printf("%I64dn",qu[i].anw);
}
return 0;
}

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <ctime>
#include <iomanip>
#pragma comment(linker,"/STACK:1024000000");
#define EPS (1e-6)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define mod 1000000007
/** I/O Accelerator Interface .. **/
#define g (c=getchar())
#define d isdigit(g)
#define p x=x*10+c-'0'
#define n x=x*10+'0'-c
#define pp l/=10,p
#define nn l/=10,n
template<class T> inline T& RD(T &x)
{
char c;
while(!d);
x=c-'0';
while(d)p;
return x;
}
template<class T> inline T& RDD(T &x)
{
char c;
while(g,c!='-'&&!isdigit(c));
if (c=='-')
{
x='0'-g;
while(d)n;
}
else
{
x=c-'0';
while(d)p;
}
return x;
}
inline double& RF(double &x)
//scanf("%lf", &x);
{
char c;
while(g,c!='-'&&c!='.'&&!isdigit(c));
if(c=='-')if(g=='.')
{
x=0;
double l=1;
while(d)nn;
x*=l;
}
else
{
x='0'-c;
while(d)n;
if(c=='.')
{
double l=1;
while(d)nn;
x*=l;
}
}
else if(c=='.')
{
x=0;
double l=1;
while(d)pp;
x*=l;
}
else
{
x=c-'0';
while(d)p;
if(c=='.')
{
double l=1;
while(d)pp;
x*=l;
}
}
return x;
}
#undef nn
#undef pp
#undef n
#undef p
#undef d
#undef g
using namespace std;
struct N
{
int l,p;
}st[200010];
int far[200010];
int Max[800100];
int dis[200010];
int Val[800100];
LL cost[200100];
int Init(int site,int l,int r)
{
if(l == r)
return Val[site] = st[l].l+st[l].p;
int mid = (l+r)>>1;
return Val[site] = max(Init(site<<1,l,mid),Init(site<<1|1,mid+1,r));
}
void Update(int site,int l,int r,int x,int d)
{
if(l == r)
{
Max[site] = max(Max[site],d);
return ;
}
int mid = (l+r)>>1;
if(x <= mid)
Update(site<<1,l,mid,x,d);
else
Update(site<<1|1,mid+1,r,x,d);
Max[site] = max(Max[site<<1],Max[site<<1|1]);
}
int Query(int site,int L,int R,int l,int r)
{
if(L == l && R == r)
return Max[site];
int mid = (L+R)>>1;
if(r <= mid)
return Query(site<<1,L,mid,l,r);
if(mid < l)
return Query(site<<1|1,mid+1,R,l,r);
return max(Query(site<<1,L,mid,l,mid),Query(site<<1|1,mid+1,R,mid+1,r));
}
int Query1(int site,int L,int R,int l,int r)
{
if(L == l && R == r)
return Val[site];
int mid = (L+R)>>1;
if(r <= mid)
return Query1(site<<1,L,mid,l,r);
if(mid < l)
return Query1(site<<1|1,mid+1,R,l,r);
return max(Query1(site<<1,L,mid,l,mid),Query1(site<<1|1,mid+1,R,mid+1,r));
}
int BS(LL x,int s,int e)
{
int mid , site = 0;
while(s <= e)
{
mid = (s+e)>>1;
if(st[mid].p <= x)
s = mid+1,site = mid;
else
e = mid-1;
}
return site;
}
void Cal(int x,int n)
{
int site = BS(st[x].l+st[x].p,x,n);
if(site == x)
far[x] = x;
else if(site == n)
far[x] = n;
else
far[x] = Query(1,1,n,x,site);
Update(1,1,n,x,far[x]);
}
int FindSite(int x,int l,int r)
{
int mid,site = r;
while(l <= r)
{
mid = (l+r)>>1;
if(far[mid] == x)
site = min(site,mid);
if(far[mid] < x)
l = mid+1;
else
r = mid-1;
}
return site;
}
struct Qu
{
int l,r,site;
LL anw;
}qu[200010];
bool cmp1(Qu q1,Qu q2)
{
return q1.l < q2.l;
}
bool cmp2(Qu q1,Qu q2)
{
return q1.site < q2.site;
}
struct Co
{
int id;
bool mark;
}cov[800100];
void InitCo(int site,int l,int r)
{
if(l == r)
{
cov[site].id = l,cov[site].mark = true;
return ;
}
int mid =(l+r)>>1;
InitCo(site<<1,l,mid);
InitCo(site<<1|1,mid+1,r);
if(cov[site<<1].id == cov[site<<1|1].id && cov[site<<1].id != -1)
cov[site].mark = true,cov[site].id = cov[site<<1].id;
else
cov[site].mark = false,cov[site].id = -1;
}
void UpdateCo(int site,int L,int R,int l,int r,int id)
{
if(L == l && R == r)
{
cov[site].mark = true;
cov[site].id = id;
return ;
}
int mid = (L+R)>>1;
if(cov[site].mark == true)
{
cov[site<<1] = cov[site];
cov[site<<1|1] = cov[site];
cov[site].mark = false;
cov[site].id = -1;
}
if(r <= mid)
UpdateCo(site<<1,L,mid,l,r,id);
else if(mid < l)
UpdateCo(site<<1|1,mid+1,R,l,r,id);
else
{
UpdateCo(site<<1,L,mid,l,mid,id);
UpdateCo(site<<1|1,mid+1,R,mid+1,r,id);
}
if(cov[site<<1].id == cov[site<<1|1].id && cov[site<<1].id != -1)
cov[site].mark = true,cov[site].id = cov[site<<1].id;
else
cov[site].mark = false,cov[site].id = -1;
}
int QueryCo(int site,int L,int R,int x)
{
if(cov[site].mark )
return cov[site].id;
int mid = (L+R)>>1;
if(x <= mid)
return QueryCo(site<<1,L,mid,x);
else
return QueryCo(site<<1|1,mid+1,R,x);
}
int main()
{
int n,i,j,q;
scanf("%d",&n);
for(i = 1;i <= n; ++i)
scanf("%d %d",&st[i].p,&st[i].l);
memset(Max,0,sizeof(Max));
Update(1,1,n,n,n);
for(far[n] = n,i = n-1; i >= 1; --i)
Cal(i,n);
Init(1,1,n);
for(i = 1;i <= n; ++i)
dis[i] = Query1(1,1,n,i,far[i]);
for(cost[n] = 0,i = n-1;i >= 1; --i)
{
if(far[i] == n)
cost[i] = 0;
else
cost[i] = cost[far[i]+1] + st[far[i]+1].p - dis[i];
}
scanf("%d",&q);
int site;
for(i = 1;i <= q; ++i)
{
scanf("%d %d",&qu[i].l,&qu[i].r);
qu[i].site = i;
}
sort(qu+1,qu+q+1,cmp1);
InitCo(1,1,n);
for(j = q,i = n;i >= 1; --i)
{
UpdateCo(1,1,n,i,far[i],i);
while(j >= 1 && qu[j].l == i)
{
if(far[i] >= qu[j].r)
qu[j].anw = 0;
else
{
site = QueryCo(1,1,n,qu[j].r);
if(far[i] >= site)
qu[j].anw = 0;
else
qu[j].anw = cost[i] - cost[site];
}
j--;
}
}
sort(qu+1,qu+q+1,cmp2);
for(i = 1;i <= q; ++i)
{
printf("%I64dn",qu[i].anw);
}
return 0;
}