Submission #1307577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307577		bbeksneckk	Arranging Tickets (JOI17_arranging_tickets)	Pypy 3	0 / 100	139 ms	48596 KiB

arranging_tickets

import sys

# Увеличиваем лимит рекурсии на всякий случай, хотя используем итеративный подход
sys.setrecursionlimit(200000)

def solve():
    # Быстрый ввод
    input = sys.stdin.read
    data = input().split()
    iterator = iter(data)
    
    try:
        N = int(next(iterator))
        M = int(next(iterator))
    except StopIteration:
        return

    requests = []
    # Считываем запросы
    for _ in range(M):
        u = int(next(iterator))
        v = int(next(iterator))
        c = int(next(iterator))
        
        if u == v:
            continue
            
        # Нормализуем путь как линейный отрезок [start, end)
        # Билет i соединяет станции i и i+1.
        # Станции нумеруются 1..N. Билеты 1..N.
        # Путь от u до v по линейке (без перехода N-1) занимает билеты
        # с индексами от min(u, v) до max(u, v) - 1.
        # Индексы билетов делаем 0-based: 1 -> 0 ... N -> N-1
        
        start = min(u, v)
        end = max(u, v)
        
        # Длина линейного пути
        linear_len = end - start
        # Длина пути через границу (обходного)
        cross_len = N - linear_len
        
        # Мы храним запросы в формате:
        # (Длина обходного пути, левая граница билетов, правая граница билетов, кол-во людей)
        # Левая граница включительно, правая не включительно (Python style range)
        # Билет i (1-based) -> индекс i-1
        requests.append((cross_len, start - 1, end - 1, c))

    # Сортируем запросы: сначала выгоднее перекидывать те, у которых обходной путь короче
    # (они меньше нагружают систему при перевороте)
    requests.sort(key=lambda x: x[0])

    # 1. Строим базовую нагрузку (все идут линейно)
    # Используем разностный массив для быстрого построения
    diff = [0] * (N + 1)
    for _, l, r, c in requests:
        diff[l] += c
        diff[r] -= c
    
    base_load = [0] * N
    curr = 0
    for i in range(N):
        curr += diff[i]
        base_load[i] = curr

    # 2. Дерево отрезков для отслеживания максимума
    # Размер дерева должен быть степенью двойки
    size = 1
    while size < N:
        size *= 2
    
    tree = [0] * (2 * size)
    lazy = [0] * (2 * size)

    # Построение дерева
    def build():
        for i in range(N):
            tree[size + i] = base_load[i]
        for i in range(size - 1, 0, -1):
            tree[i] = max(tree[2*i], tree[2*i+1])

    build()

    def update(l, r, val):
        # Итеративное обновление на отрезке [l, r)
        l += size
        r += size
        l0, r0 = l, r
        
        while l < r:
            if l & 1:
                apply(l, val)
                l += 1
            if r & 1:
                r -= 1
                apply(r, val)
            l //= 2
            r //= 2
            
        # Обновление пути к корню
        l, r = l0, r0
        while l > 1:
            l //= 2
            r //= 2 # для r не нужно точное соответствие, просто поднимаемся
            # Для корректного обновления родителей нужно пройтись по всем затронутым
            # Но в итеративном варианте с lazy проще сделать pull после всего
            pass
        
        # Полный пересчет затронутых веток (медленнее, но надежнее для max)
        # Оптимизированный вариант:
        l = l0
        r = r0 - 1
        while l > 1:
            l //= 2
            push_up(l)
        while r > 1:
            r //= 2
            push_up(r)

    def apply(idx, val):
        tree[idx] += val
        lazy[idx] += val

    def push_up(idx):
        # Значение узла = max(детей) + собственное lazy
        # Важно: lazy не спускаем вниз в этой реализации, а учитываем при чтении
        # Но для max операции lazy нужно прибавлять к результату детей
        val_left = tree[2*idx]
        val_right = tree[2*idx+1]
        tree[idx] = max(val_left, val_right) + lazy[idx]

    # Начальный ответ (без переворотов)
    min_max_load = tree[1]
    
    current_global_offset = 0
    
    # 3. Жадный перебор
    for _, l, r, c in requests:
        # Переворачиваем запрос:
        # Вместо пути [l, r) (линейного) используем дополнение.
        # Математически: Load_new = Load_old + C (везде) - 2C (на отрезке [l, r))
        
        # Добавляем C глобально (просто в переменную)
        current_global_offset += c
        
        # Вычитаем 2C на отрезке [l, r) в дереве
        update(l, r, -2 * c)
        
        # Текущий максимум = Максимум в дереве + глобальное смещение
        current_max = tree[1] + current_global_offset
        if current_max < min_max_load:
            min_max_load = current_max

    print(min_max_load)

if __name__ == '__main__':
    solve()

Compilation message (stdout)

Compiling 'arranging_tickets.py'...

=======
  adding: __main__.pyc (deflated 45%)

=======

• Subtask 1: 0 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15