CF Round310 Div1 C : Case of Chocolate

問題

http://codeforces.com/problemset/problem/555/C
n×nのグリッド上にチョコレートがある。
直線:x+y=n+1上の点からスタートして上または左に食べ進んでいく。
すでに訪問済みの座標にくるまで直進していく。
座標と方向のクエリが与えられるので、各クエリごとに何個のチョコレートを食べることができるかを求める問題。

解法

(sx,sy)から上に進む場合を考える。
この時、今までのクエリの開始地点のx座標の中でsxより大きいものの中で最小の座標mxを求める。そのクエリq'が
・上方向のクエリだったら、xからmxの間にあるチョコレートに対するクエリは存在しないので、q'が進めた分 + mxとxとの距離 が食べられるチョコレートの数となる。
・左方向のクエリだったら、そのクエリの開始座標のy座標まで進める。
つまりq'を二分探索で求めれば良い。