破滅 10:00 開始 A が永遠に解けず、11:31 まで粘着する 諦めて B に行き、13:03 に解ける A に行って頑張るが解けないので、点数最大化のために C に行って、一瞬で部分点 12 点が取れたので、取る これが 13:41 残り全部 A に粘着したけど解けず 112点 破…

問題リンク 解説 辺 $(u, v)$ を反転させるとき、$(u, v)$ が消えて $(v, u)$ が追加される。 このとき、追加した辺を利用した最短距離は、先にダイクストラ法で前計算しておけば簡単に求められる。 しかし、辺が削除されることには対応できない。 辺が削除…

問題リンク 解説 時系列順に数列の様子を並べると，同じ数でできた三角形や平行四辺形の集合になるので，これを頑張ってセグ木で再現する． 平行四辺形に差し引きすると直角二等辺三角形と長方形にできるので，これらの加算ができればよい． 長方形の加算は…

問題リンク 解説 小課題から消化していく． 小課題 1 愚直に実装すればよい．$O(N^2Q)$ で解ける． 小課題 2 すべてのペアについて探索すると，グリッド上での長方形内の最大を求める問題になる．2次元セグ木を書くと，$O(N^2+Q\log^2N)$ で解ける． 小課題 …

問題リンク 解説 木上の始点が根に固定されたパスについて， パス上の頂点の値を並べたときの転倒数を求める パス上の頂点の値をすべてある値に更新する という操作を繰り返し行う． すでに操作されたパスの部分パスが操作されることはない． さて，転倒数を…

問題リンク 解説 まず，濃さ $D$ のリンゴが入荷したら，配列の $[D, D+M]$ に $1$ 加算して，$N$ 個の出荷クエリが来た時は，配列のうちで $N$ 以上の最も右の値が取れれば良い． 出荷するべきリンゴは std::set などで容易に求められるので，出荷するとき…