Submission #57894449

---

Source Code Expand

from functools import cmp_to_key
import sys

input = sys.stdin.readline


def floor_sum(n, m, a, b):
    a1, a2 = a // m, a % m
    ans = n * (n - 1) // 2 * a1
    if a2 == 0:
        return ans + b // m * n
    b1, b2 = b // m, b % m
    y = (a2 * n + b2) // m
    ans += n * (y + b1) - floor_sum(y, a2, m, m + a2 - b2 - 1)
    return ans


def cmp(d1, d2):
    a1, b1, c1 = d1
    a2, b2, c2 = d2
    if a1 * b2 != a2 * b1:
        return a1 * b2 - a2 * b1
    return c1 * a2 - c2 * a1


def clamp(x, l, r):
    return min(r, max(l, x))


for _ in range(int(input())):
    N = int(input())
    L = [tuple(map(int, input().split())) for _ in range(N)]
    L.sort(key=cmp_to_key(cmp))
    co = []
    x = []
    INF = 10**18
    x_lim = INF
    for l in L:
        aj, bj, cj = l
        if len(co) >= 1:
            ai, bi, ci = co[-1]
            if ai * bj == aj * bi:
                continue
        while len(co) >= 2:
            ai, bi, ci = co[-1]
            xj = (bi * cj - bj * ci - 1) // (aj * bi - ai * bj) + 1
            if xj > x[-1]:
                break
            co.pop()
            x.pop()
        co.append(l)
        if len(x) == 0:
            x.append(-INF)
        else:
            ai, bi, ci = co[-2]
            xj = (bi * cj - bj * ci - 1) // (aj * bi - ai * bj) + 1
            x.append(xj)
        x_lim = min(x_lim, (cj + aj - 1) // aj)
    x.append(INF)
    ans = 0
    for i in range(len(co)):
        ai, bi, ci = co[i]
        le, ri = clamp(x[i], 1, x_lim), clamp(x[i + 1], 1, x_lim)
        n, m, a, b = ri - le, bi, ai, ci - 1 - ai * (ri - 1)
        ans += floor_sum(n, m, a, b % m) + (b // m) * n
    print(ans)

Submission Info

Judge Result