AT_abc260_g [ABC260G] Scalene Triangle Area

[problemUrl]: https://atcoder.jp/contests/abc260/tasks/abc260_g $ N\ \times\ N $ のグリッドがあり、このグリッドの上から $ i $ マス目、左から $ j $ マス目を $ (i,j) $ と呼びます。 このグリッドの各マスには高々 $ 1 $ 個のコマが置かれています。 グリッドの状態は $ N $ 個の文字列 $ S_i $ として与えられ、 - $ S_i $ の $ j $ 文字目が `O` であるとき $ (i,j) $ に $ 1 $ つコマが置かれていること - $ S_i $ の $ j $ 文字目が `X` であるとき $ (i,j) $ にコマは置かれていないこと を表します。 整数 $ M $ が与えられます。 この $ M $ を使って、 $ (s,t) $ に置かれているコマ $ P $ について、以下の条件を全て満たすマス $ (u,v) $ を $ P $ が守っているマスと定義します。 - $ s\ \le\ u\ \le\ N $ - $ t\ \le\ v\ \le\ N $ - $ (u\ -\ s)\ +\ \frac{(v\ -\ t)}{2}\

N/A

N/A

### 制約 - $ N,M,X_i,Y_i,Q $ は整数 - $ 1\ \le\ N\ \le\ 2000 $ - $ 1\ \le\ M\ \le\ 2\ \times\ N $ - $ S_i $ は `O`, `X` からなる - $ 1\ \le\ Q\ \le\ 2\ \times\ 10^5 $ - $ 1\ \le\ X_i,Y_i\ \le\ N $ ### Sample Explanation 1 マス $ (1,1) $ のみにコマが置かれ、このコマによって以下の `#` のマスが守られます。 ``` #### ##.. .... .... ```