yukicoder contest 304 参戦記

A 1603 Manhattan Social Distance

N=2だと(1, 1) と (H, W) に置くのが最大だなあとなり、N=3だと3個目はやっぱり (1, 1) か (H, W) に置くよなあの辺りで、(1, 1) と (H, W) に交互に置けばいいのかと分かる,

N, H, W = map(int, input().split())

print((H + W - 2) * ((N + 1) // 2 * N // 2))

B 1604 Swap Sort:ONE

答えは転倒数(蟻本では反転数)なので、過去のコードを貼る.

class BinaryIndexedTree:
    def __init__(self, size):
        self._data = [0] * size

    def add(self, i, x):
        data = self._data
        i += 1
        n = len(data)
        while i <= n:
            data[i - 1] += x
            i += i & -i

    def _sum(self, stop):
        data = self._data
        result = 0
        i = stop
        while i > 0:
            result += data[i - 1]
            i -= i & -i
        return result

    def range_sum(self, start, stop):
        return self._sum(stop) - self._sum(start)


N, *P = map(int, open(0).read().split())

bit = BinaryIndexedTree(N + 1)

result = 0
for x in P:
    result += bit.range_sum(x + 1, N + 1)
    bit.add(x, 1)
print(result)