ARC082 F : Sandglass(700)
作成日：2017.09.03
最終更新日：2017.09.03
問題概要
パーツAとパーツBからなる砂時計に砂が$X$グラム入っている。
砂時計は一方のパーツが上、もう一方のパーツが下になるように置かれ、$1$秒間に$1$グラムの砂が上のパーツから砂がなくなるまで下のパーツに落ちる。
砂時計は時刻$0$にパーツAが上にあり、時刻$r_i$に瞬間的にひっくり返す。
$Q$個のクエリ「時刻$0$にパーツAに$a_i$グラムの砂が入っていた時、時刻$t_i$にパーツAに入っている砂の量を求めよ」に答えよ。
制約
$1 \leq X \leq 10^9$
$1 \leq K \leq 10^5$
$1 \leq r_1 < r_2 < ... < r_K \leq 10^9$
$1 \leq Q \leq 10^5$
$0 \leq t_1 < t_2 < ... < t_Q \leq 10^9$
$0 \leq a_i \leq X$
入力はすべて整数
考え方
愚直に求めると計算量は$O(KQ)$となり間に合わないので工夫する。
そのために$t_i$よりも変化させた状態が考えにくい$a_i$をまとめて考えることにする。
パーツAに入っている砂は時刻$r_1$まで減少するが、途中で空になった場合は減少しなくなる。
途中で空になった場合はその後は同じようにふるまうため、まとめて考えることができ、そうなるのは$a_i \leq r_1$の時である。
途中で空にならなかった場合は、残りの砂の量は異なるが減少した砂の量は等しい。
よってこの時もまとめて考えることができる。
時刻$r_1$から時刻$r_2$までの場合も同様に考えると、パーツBが途中で空になるか否かでそれぞれまとめて考えられる。
時刻$r_2$以降も同様に考えれば、パーツAが途中で空になった場合、パーツBが途中で空になった場合、いずれでもない場合の3つにまとめることができる。
また、まとめる$a_i$の範囲は区間で表されるので、時刻$r_i$ごとに境界を保持していれば良い。
時系列順にその区間を更新しながらクエリに答えれば計算量は$O(K+Q)$となり十分高速である。
ソースコード
マクロ等はこちら
const int MC = 100010;
int X,K,Q;
int r[MC];
int t[MC] , a[MC];
int amin,amax;
int ansmin,ansmax;
int ans[MC];
int main(){
scanf("%d%d" , &X , &K);
repp(i,1,K+1){
scanf("%d" , r + i);
}
scanf("%d" , &Q);
repp(i,0,Q){
scanf("%d%d" , t + i , a + i);
}
amin = ansmin = 0;
amax = ansmax = X;
int pt = 0;
int sum = 0;
repp(i,0,K){
int z = (i%2?1:-1);
while(pt < Q && t[pt] < r[i+1]){
if(a[pt] < amin) ans[pt] = max(0,min(X,ansmin+z*(t[pt]-r[i])));
else if(a[pt] > amax) ans[pt] = max(0,min(X,ansmax+z*(t[pt]-r[i])));
else ans[pt] = max(0,min(X,a[pt]+sum+z*(t[pt]-r[i])));
++pt;
}
sum += z*(r[i+1]-r[i]);
if(sum > X) sum = X;
if(sum < -X) sum = -X;
amin = max(amin,min(X,-sum));
amax = min(amax,max(0,X-sum));
ansmin = max(0,min(X,ansmin+z*(r[i+1]-r[i])));
ansmax = max(0,min(X,ansmax+z*(r[i+1]-r[i])));
}
int z = (K%2?1:-1);
while(pt < Q){
if(a[pt] < amin) ans[pt] = max(0,min(X,ansmin+z*(t[pt]-r[K])));
else if(a[pt] > amax) ans[pt] = max(0,min(X,ansmax+z*(t[pt]-r[K])));
else ans[pt] = max(0,min(X,a[pt]+sum+z*(t[pt]-r[K])));
++pt;
}
repp(i,0,Q){
printf("%d\n" , ans[i]);
}
return 0;
}解法まとめ
時系列に沿って処理する。
パーツAが途中で空になった場合、パーツBが途中で空になった場合、いずれでもない場合の3つに$a_i$を分類し、それぞれの場合の答えを保持しながらクエリに答える。(18-44行)