ARC082D Sandglass

题意:有一个沙漏由A,B两个杯子组成。一共有X克沙子。
每秒会有一克沙子从上杯子流到下杯子,直到流完为止。

一共会有k次翻转杯子,第i次翻转杯子会在第 $r_i$ 秒。

有q组询问,每组形如 $t,a$ ,表示一开始A杯子在上,里面有a克沙子(B杯子里有 $X-a$ 克沙子),求第t秒的时候A杯子里有多少沙子。
$q,k\le 10^5$

$q,k\le 10^5$ ,暴力是一定会超时的。所以我们要想想办法。

计算当一开始里A杯子有s克沙子杯子里有$l$克沙子的时候第$r_i$秒时A里面的沙子量。

可以发现:1的时候为$\max\{s-r_1,0\}$,等等。

然后会发现每一次A里面的沙子量可以表示为$\max\{\min\{s+a,b\},c\}$,其中$a,b,c$都是常数,

所以我们可以找一波递推公式。

用$(a,b,c)$表示$\max\{\min\{s+a,b\},c\}$。
设每次流沙子的时间为d。
发现当第奇数次翻转的时候,沙子量会从$(a,b,c)$变为$\max\{\max\{\min\{s+a,b\},c\}-d,0\}$,第偶数次的时候会变成$\min\{\max\{\min\{s+a,b\},c\}+d,l\}$,暴力拆一波式子得到第奇数次翻转的时候变为$(a-d,b-d,\max\{c-d,0\})$,第偶数次翻转的时候变为$(a+d,min\{\max\{b,c\}+d,l\},\min\{c+d,l\})$。

求出每一次的a,b,c以后,对每组询问二分查找一下在第t秒之前最后一次翻转,这次翻转之前A杯子里有多少沙子,然后再一波$O(1)$计算一下就可以了(毕竟没有翻转直接流当然$O(1)$)

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
/*
Author: CNYALI_LK
LANG: C++
PROG: F.cpp
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
int r[102424];
int t[102424],y[102424];
int a[102424],b[102424],c[102424];
#define min mmin
#define max mmax
#define abs aabs
int main(){
#ifdef cnyali_lk
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int l,k,q,d;
a[0]=0;
b[0]=0x3f3f3f3f;
c[0]=-0x3f3f3f3f;
scanf("%d%d",&l,&k);
for(int i=1;i<=k;++i)scanf("%d",r+i);
a[1]=(-r[1]);
b[1]=0x3f3f3f3f;
c[1]=0;
for(int i=2;i<=k;++i){
d=r[i]-r[i-1];
if(i&1){
a[i]=a[i-1]-d;
b[i]=b[i-1]-d;
c[i]=mmax(c[i-1]-d,0);
}
else{
a[i]=a[i-1]+d;
b[i]=mmin(mmax(b[i-1],c[i-1])+d,l);
c[i]=min(c[i-1]+d,l);
}
}
scanf("%d",&q);
for(int i=1;i<=q;++i){
scanf("%d",t+i);
int lx,rx,mid;
scanf("%d",y+i);
lx=0;rx=k;
while(lx<=rx){
mid=(lx+rx)>>1;
if(t[i]>=r[mid])lx=mid+1;
else rx=mid-1;
}
--lx;
t[i]-=r[lx];
y[i]=max(min(y[i]+a[lx],b[lx]),c[lx]);
if(lx&1){
y[i]=min(y[i]+t[i],l);
}
else{
y[i]=max(y[i]-t[i],0);
}
printf("%d\n",y[i]);
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×