Toyota Programming Contest 2024#4（AtCoder Beginner Contest 348）F,G問題メモ

import os
import sys

import numpy as np


def solve(inp):
    def bit_count(arr):
        t = arr.dtype.type
        mask = t(-1)
        s55 = t(0x5555555555555555 & mask)  # Add more digits for 128bit support
        s33 = t(0x3333333333333333 & mask)
        s0F = t(0x0F0F0F0F0F0F0F0F & mask)
        s01 = t(0x0101010101010101 & mask)

        arr = arr - ((arr >> 1) & s55)
        arr = (arr & s33) + ((arr >> 2) & s33)
        arr = (arr + (arr >> 4)) & s0F
        return (arr * s01) >> (8 * (arr.itemsize - 1))

    n, m = inp[:2]
    k = (n - 1) // 61 + 1
    d = np.zeros((m, 1000, k), np.int64)
    result = np.zeros((n, k), np.int64)
    for i in range(n):
        p, q = divmod(i, 61)
        bit = 1 << q
        for j in range(m):
            a = inp[i * m + j + 2]
            result[i] ^= d[j, a]
            d[j, a, p] |= bit

    ans = bit_count(result).sum()
    return ans


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

from itertools import accumulate
from operator import itemgetter
from typing import Callable, List


def smawk(n: int, m: int, select: Callable[[int, int, int], bool]) -> List[int]:
    """
    n×m 配列 A の、各行における最小値(※)を与える列index [j1,j2,...,jn] を得る。

    制約:
      A はTotally Monotone
      A は陽に与える必要は無く、比較関数 select によって評価する
        select(i,j,k) := A[i,j] > A[i,k] なら True を返す関数

    (※)
    最小値以外（最大値など）の指標にも適用できる。
    Aはその指標にとっての Totally Monotone であればよく、select(i,j,k) はA[i,k]の方が"よい"場合にTrueを返す関数とする。

    参考:
      https://github.com/noshi91/Library/blob/master/algorithm/smawk.cpp
    """
    columns_history = [list(range(m))]
    row_bit_length = n.bit_length()
    for depth in range(row_bit_length):
        next_row_size = n >> depth
        i_step = 1 << depth
        i = i_step - 1
        columns = []
        for j in columns_history[depth]:
            while columns and select(i - i_step, columns[-1], j):
                columns.pop()
                i -= i_step
            if len(columns) < next_row_size:
                columns.append(j)
                i += i_step
        columns_history.append(columns)

    assert len(columns_history[row_bit_length]) == 1

    result = [0] * n
    result[(1 << (row_bit_length - 1)) - 1] = columns_history[row_bit_length][0]

    for depth in range(row_bit_length - 1, 0, -1):
        i_step = 1 << depth
        h_step = i_step >> 1
        columns = columns_history[depth]
        ji = 0
        for i in range(h_step - 1, n, i_step):
            res = columns[ji]
            until = columns[-1] if i + h_step >= n else result[i + h_step]
            while columns[ji] < until:
                ji += 1
                if select(i, res, columns[ji]):
                    res = columns[ji]
            result[i] = res

    return result


def get_score(dp, acc, w, l, i, j):
    if j == 0:
        return dp[l + i - 1]
    else:
        return acc[l + w] - acc[l + w - (i - j)] + dp[l + w + j - 1]


def solve(n, ab):
    ab.sort(key=itemgetter(1))
    aaa, bbb = zip(*ab)
    # dp[w][i*w+j] = 左端が i*w から始まる長さ w の区間から j+1 個選んだときの最大値 (w=1,2,4,... j=0,1,...,w-1)、w は省略
    dp = [a - b for a, b in ab]
    acc = [0] + list(accumulate(aaa))
    w2 = 2

    while (w2 >> 1) <= n:
        w = w2 >> 1
        ndp = [0] * n
        sorted_aaa = [0] * n
        l = 0
        while l < n:
            mid = l + w
            if mid < n:
                r = min(l + w2, n)
                m = r - l
                right_limit = r - mid

                def select(i, j, k):
                    i += 1
                    if i - j > w:
                        return True
                    if i < k or k > right_limit:
                        return False
                    return get_score(dp, acc, w, l, i, j) < get_score(dp, acc, w, l, i, k)

                res = smawk(m, m + 1, select)

                for i in range(r - l):
                    ndp[l + i] = get_score(dp, acc, w, l, i + 1, res[i])

                # aaa のソート
                i = l
                j = mid
                k = l
                while i < mid and j < r:
                    if aaa[i] <= aaa[j]:
                        sorted_aaa[k] = aaa[i]
                        i += 1
                        k += 1
                    else:
                        sorted_aaa[k] = aaa[j]
                        j += 1
                        k += 1
                if i < mid:
                    sorted_aaa[k:r] = aaa[i:mid]
                else:
                    sorted_aaa[k:r] = aaa[j:r]

            else:
                ndp[l:] = dp[l:]
                sorted_aaa[l:] = aaa[l:]

            l += w2

        dp = ndp
        aaa = sorted_aaa
        acc = [0] + list(accumulate(aaa))
        w2 <<= 1

    return dp


n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n)]
ans = solve(n, ab)
print('\n'.join(map(str, ans)))