AtCoder Beginner Contest 218 C,F,G,H問題メモ

from itertools import dropwhile


def trim(sss):
    for _ in range(4):
        sss = list(dropwhile(lambda row: all(c == '.' for c in row), sss))
        sss = list(zip(*reversed(sss)))
    return sss


n = int(input())
sss = [tuple(input()) for _ in range(n)]
ttt = [tuple(input()) for _ in range(n)]

sss = trim(sss)
ttt = trim(ttt)

for _ in range(4):
    if sss == ttt:
        print('Yes')
        break
    sss = list(zip(*reversed(sss)))
else:
    print('No')

from collections import deque

n, m = map(int, input().split())
links = [set() for _ in range(n)]
edges = []
for i in range(m):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    links[s].add(i)
    rev_links[t].add(i)
    edges.append((s, t))

INF = 1 << 60
trace = [-1] * n
result = [INF] * n
q = deque()
q.append(0)
result[0] = 0
g = n - 1
while q:
    v = q.popleft()
    if v == g:
        break
    for i in links[v]:
        u = edges[i][1]
        if result[u] <= result[v] + 1:
            continue
        result[u] = result[v] + 1
        trace[u] = i
        if u == g:
            break
        q.append(u)
    else:
        continue
    break

if result[g] == INF:
    print(*([-1] * m))
    exit()

shortest_edges = set()
u = g
while u != 0:
    i = trace[u]
    shortest_edges.add(i)
    u = edges[i][0]

d = result[n - 1]
for i in range(m):
    if i not in shortest_edges:
        print(d)
        continue

    tmp_result = [INF] * n
    tmp_result[0] = 0
    q = deque()
    q.append(0)
    while q:
        v = q.popleft()
        for j in links[v]:
            if i == j:
                continue
            u = edges[j][1]
            if tmp_result[u] <= tmp_result[v] + 1:
                continue
            tmp_result[u] = tmp_result[v] + 1
            if u == g:
                break
            q.append(u)
        else:
            continue
        break
    if tmp_result[g] == INF:
        print(-1)
    else:
        print(tmp_result[g])

import sys

from operator import add, lt

sys.setrecursionlimit(2 * 10 ** 5)


class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()

    def add(self, i, x):
        i += 1
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i

    def sum(self, i):
        i += 1
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s

    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和

        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k > self.size:
                continue
            new_total = func(total, tree[k])
            if lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos

    def debug_print(self):
        prev = 0
        arr = []
        for i in range(self.size):
            curr = self.sum(i)
            arr.append(curr - prev)
            prev = curr
        print(arr)


n = int(input())
aaa = list(map(int, input().split()))
links = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].append(b)
    links[b].append(a)

aaa_list = sorted(set(aaa))
aaa_dict = {a: i for i, a in enumerate(aaa_list)}

fwt = FenwickTreeInjectable(len(aaa_list), int, add)


def dfs(v, p, depth, fwt: FenwickTreeInjectable):
    a = aaa[v]
    i = aaa_dict[a]
    fwt.add(i, 1)

    if v != 0 and len(links[v]) == 1:
        if depth % 2 == 0:
            j = fwt.lower_bound(depth // 2 + 1, lt)
            res = aaa_list[j]
        else:
            j1 = fwt.lower_bound(depth // 2 + 1, lt)
            j2 = fwt.lower_bound(depth // 2 + 2, lt)
            res = (aaa_list[j1] + aaa_list[j2]) // 2
        fwt.add(i, -1)
        return res

    if depth % 2 == 0:
        cmp = max
        res = -1
    else:
        cmp = min
        res = 1 << 60

    for u in links[v]:
        if u == p:
            continue

        res = cmp(res, dfs(u, v, depth + 1, fwt))

    fwt.add(i, -1)

    return res


ans = dfs(0, -1, 0, fwt)
print(ans)

from heapq import heapify, heappop, heappush

n, r = map(int, input().split())
aaa = list(map(int, input().split()))

if r * 2 > n:
    r = n - r
elif r * 2 == n:
    print(sum(aaa))
    exit()

q = [(-aaa[i] - aaa[i + 1], i, i + 1) for i in range(n - 2)]
heapify(q)

used = [False] * (n - 1)
lefts = list(range(-1, n - 1))
rights = list(range(1, n + 1))
ans = 0

while r:
    a, i, j = heappop(q)

    if used[i] or used[j]:
        continue

    ans += -a
    used[i] = used[j] = True
    ni = lefts[rights[j]] = lefts[i]
    nj = rights[lefts[i]] = rights[j]
    r -= 1

    if ni == -1 or nj == n - 1:
        continue

    heappush(q, (-aaa[ni] - aaa[nj], ni, nj))

print(ans)