AtCoder Beginner Contest 478 E,F,G問題メモ

from atcoder.scc import SCCGraph


def solve(n, q, conditions):
    cond0 = []
    cond1 = []
    for t, u, v in conditions:
        u -= 1
        v -= 1
        if t == 0:
            cond0.append((u, v))
        else:
            cond1.append((u, v))
    scg = SCCGraph(n)
    for u, v in cond0:
        scg.add_edge(u, v)
    result = scg.scc()
    tmp = [0] * n
    for i, grp in enumerate(result):
        for v in grp:
            tmp[v] = i
    scg2 = SCCGraph(len(result))
    for u, v in cond1:
        if tmp[u] == tmp[v]:
            return False
        scg2.add_edge(tmp[u], tmp[v])
    for u, v in cond0:
        if tmp[u] == tmp[v]:
            continue
        scg2.add_edge(tmp[u], tmp[v])
    result2 = scg2.scc()
    ans = [0] * n
    for i, grp in enumerate(result2, start=1):
        if len(grp) >= 2:
            return False
        w = grp[0]
        for v in result[w]:
            ans[v] = i
    return ans


n, q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(q)]
ans = solve(n, q, edges)
if ans:
    print('Yes')
    print(*ans)
else:
    print('No')

from atcoder.segtree import SegTree


def solve(n, qqq):
    MOD = 998244353
    sgt = SegTree(max, -1, qqq)
    ans = 1
    for i in range(1, n):
        q = qqq[i]
        j = sgt.min_left(i, lambda a: a < q)
        if j == 0:
            cf = i
        else:
            cf = i - j + 1
        ans *= cf
        ans %= MOD
    return ans


n = int(input())
qqq = list(map(int, input().split()))
ans = solve(n, qqq)
print(ans)

from math import gcd


def cross(o, a, b):
    """ (a-o) × (b-o)。左折で正、右折で負、共線（重複含む）で 0
        b         :正
    o------>a  b  :0
        b         :負
    """
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


def monotone_chain(points, lower: bool):
    """ Andrew's Monotone Chain により凸包（の片側）を求める。
    points は [(x,y),(x,y),...] の列で、(x,y) でソート済みとする。軸は x→, y↑ を正とする。
    lower=True なら下側凸包、lower=False なら上側凸包を求める。
    """
    # Tips:
    # 複数の片側凸包のマージも、配列結合・ソートしてこれを呼ぶのが速い。
    # Python の sort は昇順の連続区間1つを run として概ね O(N log [runの本数]) なので、ほぼ線形に動作する。
    h = []
    sign = 1 if lower else -1
    for p in points:
        while len(h) >= 2 and sign * cross(h[-2], h[-1], p) <= 0:
            h.pop()
        h.append(p)
    if len(h) == 2 and h[0] == h[1]:
        h.pop()
    return h


def merge_chain_vector(h1, h2, lower: bool):
    """ 片側凸包 2 つをベクトル合成する。
    h1, h2 は、[(x,y),(x,y),...] の列で、(x,y) でソート済みの上側または下側凸包とする。軸は x→, y↑ を正とする。
    重複は許容されない（一方に同じ点が存在してはいけない。分かれて存在するのはOK）
    S = { (x1+x2,y1+y2) | (x1,y1)∈h1, (x2,y2)∈h2 } として、S の上側/下側凸包を求める。
    lower=True なら下側凸包、lower=False なら上側凸包同士をマージする。
    Complexity: O(|h1|+|h2|)
    """
    sign = 1 if lower else -1
    n1 = len(h1)
    n2 = len(h2)
    i = j = 0
    result = [(h1[0][0] + h2[0][0], h1[0][1] + h2[0][1])]
    while i < n1 - 1 or j < n2 - 1:
        if j == n2 - 1:
            i += 1
        elif i == n1 - 1:
            j += 1
        else:
            # 上側凸包なら傾きの大きい方（下側なら小さい方）のポインタを進める
            dx1 = h1[i + 1][0] - h1[i][0]
            dy1 = h1[i + 1][1] - h1[i][1]
            dx2 = h2[j + 1][0] - h2[j][0]
            dy2 = h2[j + 1][1] - h2[j][1]
            c = sign * (dx1 * dy2 - dy1 * dx2)
            if c >= 0:
                i += 1
            if c <= 0:
                j += 1
        result.append((h1[i][0] + h2[j][0], h1[i][1] + h2[j][1]))
    return result


def polygon_area(points):
    """ 反時計回りの頂点列 [(x,y),(x,y),...] から面積「の2倍」を求める """
    n = len(points)
    if n < 3:
        return 0
    result = points[-1][0] * points[0][1] - points[0][0] * points[-1][1]
    for i in range(n - 1):
        result += points[i][0] * points[i + 1][1] - points[i + 1][0] * points[i][1]
    return result


def solve(n, p, q, points):
    def sub(l, r):
        """ points[l:r] の「内分点の上側凸包」「内分点の下側凸包」「そのままの点の上側凸包」「そのままの点の下側凸包」 """
        if r - l < 10:
            pts = sorted(points[l:r])
            orig_hi = monotone_chain(pts, False)
            orig_lo = monotone_chain(pts, True)
            pts = set()
            for i in range(l, r):
                x1, y1 = points[i]
                for j in range(i + 1, r):
                    x2, y2 = points[j]
                    pts.add((x1 * q + x2 * p, y1 * q + y2 * p))
            pts = sorted(pts)
            internal_hi = monotone_chain(pts, False)
            internal_lo = monotone_chain(pts, True)
            return internal_hi, internal_lo, orig_hi, orig_lo
        mid = (l + r) // 2
        l_int_hi, l_int_lo, l_org_hi, l_org_lo = sub(l, mid)
        r_int_hi, r_int_lo, r_org_hi, r_org_lo = sub(mid, r)
        tmp_hi = merge_chain_vector([(q * x, q * y) for x, y in l_org_hi], [(p * x, p * y) for x, y in r_org_hi], False)
        tmp_lo = merge_chain_vector([(q * x, q * y) for x, y in l_org_lo], [(p * x, p * y) for x, y in r_org_lo], True)
        int_hi = monotone_chain(sorted(l_int_hi + r_int_hi + tmp_hi), False)
        int_lo = monotone_chain(sorted(l_int_lo + r_int_lo + tmp_lo), True)
        org_hi = monotone_chain(sorted(l_org_hi + r_org_hi), False)
        org_lo = monotone_chain(sorted(l_org_lo + r_org_lo), True)
        return int_hi, int_lo, org_hi, org_lo

    h_hi, h_lo, _, _ = sub(0, n)
    h_hi.reverse()
    hull = h_lo[:-1] + h_hi[:-1]
    ans_num = polygon_area(hull)
    ans_div = (p + q) ** 2 * 2
    g = gcd(ans_num, ans_div)
    ans_num //= g
    ans_div //= g
    return ans_num, ans_div


n, p, q = list(map(int, input().split()))
points = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, p, q, points)
print(*ans)