Shou Ohba
Shou Ohba
#816 を作りました。元の制約だと想定解が 1.3 秒程度だったので、制約を $N\leq 100000,Q\leq 200000$ に落としました。 制約変更後の想定解でも500ms程度掛かっていますが、もう少し制約を落としたほうが良いでしょうか？前計算の $N\log N$ の定数倍が酷くてここがボトルネックになっているので、さらに制約を落とすとしたら $N$ を小さくすることになると思います。
問題名: Vertex Get Range Contour Add On Tree 問題ID: vertex_get_range_contour_add_on_tree #816 の双対 (?) ## 問題 $N$ 頂点の木 $T$ が与えられる。 $T$ の $i$ 番目の辺は $u_i$ と $v_i$ を双方向に結ぶ重み $1$ の辺である。また、各 $i...
問題名: Vertex Add Range Contour Sum On Tree 問題ID: vertex_add_range_contour_sum_on_tree ## 問題 $N$ 頂点の木 $T$ が与えられる。 $T$ の $i$ 番目の辺は $u_i$ と $v_i$ を双方向に結ぶ重み $1$ の辺である。また、各 $i = 0, \ldots,...
問題名: Deque Operate All Composite 問題ID: deque_operate_all_composite ## 問題 長さ $0$ (一次)関数の列 $f = ()$ があります。$Q$ 個のクエリが飛んできます。処理してください。 `0` $a\ b$ : 列 $f$ の先頭に一次関数 $\lambda x. ax + b$ を追加する...
https://github.com/yosupo06/library-checker-problems/issues/783 + 遅延評価 ## Problem $N$ 頂点の辺のないグラフ $G$ がある。はじめ、頂点 $i$ には整数 $a _ i$ が書かれている。以下の形式のクエリを $Q$ 個処理。 - `0 u v`: $G$ に無向辺 $\lbrace u, v\rbrace$ を追加 - `1 v...
出力を見ると small や even_mod_impossible を除いて解無しのものが 9 割程度 (645/711) を占めていることが分かったので、ケース追加を提案します。 具体的なコーナーケース等を発見した訳ではありませんが、とりあえず解が存在するケースを増やすだけでも嬉しそうだと思いました。 ケース案: - 全て解が存在するようなケース - 素数 mod - Pohlig Hellman に不利なケース (Xの位数が小さな素因数を持たないケース？あまりちゃんと理解してません)