Problem statement

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/F

Solution 1

This segment tree will support two operations:

  1. Set values in range [l, r) as arithmetic progression with parameters a, d or add value v to value in this range.
  2. Find maximum in range [l, r)

In lazy updates we will keep pair (d, v) where d means that we need to set values to 0, d, 2d, ... and v means that after we add v to all values. If d = -inf, it means that we skip the first step.

Complexity

Standart compexities for segment tree. However it will give TLE here on python.

Code

from collections import defaultdict

class SegmentTree:
    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.ZERO = -float("inf")  # neutral element, for ma it is +inf
        self.NO_OPERATION = (float("inf"), 0)
        self.T = defaultdict(int)
        self.L = defaultdict(lambda: self.NO_OPERATION)

    def op_query(self, a, b):
        return max(a, b)

    def op_modify_L(self, h0, h1, len_):
        d, v = h1
        if d != -float("inf"):
            return d, v + d * len_
        else d == -float("inf"):
            if h0 != self.NO_OPERATION:
                return h0[0], h0[1] + v
            else:
                return h1

    def op_modify_T(self, x, h0, len_):
        d, v = h0
        if d != -float("inf"):
            return v + d * len_
        else:
            return x + v

    def propagate(self, x, lx, rx):
        if self.L[x] == self.NO_OPERATION or rx - lx == 1:
            return
        mx = (lx + rx) // 2
        d, v = self.L[x]
        self.L[2 * x + 1] = self.op_modify_L(self.L[2 * x + 1], self.L[x], 0)
        self.L[2 * x + 2] = self.op_modify_L(self.L[2 * x + 2], self.L[x], mx - lx)
        l1 = mx - lx - 1 if d > 0 else 0
        l2 = rx - lx - 1 if d > 0 else mx - lx
        self.T[2 * x + 1] = self.op_modify_T(self.T[2 * x + 1], self.L[x], l1)
        self.T[2 * x + 2] = self.op_modify_T(self.T[2 * x + 2], self.L[x], l2)
        self.L[x] = self.NO_OPERATION

    def _update(self, l, r, d, v, x, lx, rx):
        self.propagate(x, lx, rx)
        if l >= rx or lx >= r:
            return
        if lx >= l and rx <= r:
            self.L[x] = self.op_modify_L(self.L[x], (d, v), lx - l)
            l1 = rx - l - 1 if d > 0 else lx - l
            self.T[x] = self.op_modify_T(self.T[x], (d, v), l1)
            return

        mx = (lx + rx) // 2
        self._update(l, r, d, v, 2 * x + 1, lx, mx)
        self._update(l, r, d, v, 2 * x + 2, mx, rx)
        self.T[x] = self.op_query(self.T[2 * x + 1], self.T[2 * x + 2])

    def update(self, l, r, d, v):
        return self._update(l, r, d, v, 0, 0, self.size)

    def first_above_(self, v, x, lx, rx):
        self.propagate(x, lx, rx)
        if self.T[x] < v:
            return -1
        if rx - lx == 1:
            return lx
        mx = (lx + rx) // 2
        res = self.first_above_(v, 2 * x + 1, lx, mx)
        if res == -1:
            res = self.first_above_(v, 2 * x + 2, mx, rx)
        return res

    def first_above(self, v):
        return self.first_above_(v, 0, 0, self.size)

    def _get(self, i, x, lx, rx):
        self.propagate(x, lx, rx)
        if rx - lx == 1:
            return self.T[x]
        mx = (lx + rx) // 2
        if i < mx:
            return self._get(i, 2 * x + 1, lx, mx)
        else:
            return self._get(i, 2 * x + 2, mx, rx)

    def get(self, i):
        return self._get(i, 0, 0, self.size)

if __name__ == '__main__':
    n = int(input())
    STree = SegmentTree(n + 1)

    while True:
        t = input().split()
        if t[0] == "I":
            l, r, d = int(t[1]), int(t[2]), int(t[3])
            v1, v2 = STree.get(l - 1), STree.get(r)
            STree.update(l - 1, r + 1, d, v1)
            v3 = STree.get(r)
            STree.update(r + 1, n + 1, -float("inf"), v3 - v2)

        elif t[0] == "Q":
            x = STree.first_above(int(t[1]) + 1)
            if x == -1:
                print(n)
            else:
                print(x - 1)
        else:
            break

Solution 2

This solution is based on oficial solution of this problem (from IOI 2005): https://dmoj.ca/problem/ioi05p3/editorial, the second optimized solution. Idea is similar, but we can make smarter updates.

Complexity

Standart compexities for segment tree.

Code

class SegmentTree:
    def __init__(self, n):
        self.t = [0] * (n * 4)
        self.p = [0] * (n * 4)
        self.lz = [MINF] * (n * 4)

    def push(self, x, lx, rx):
        if self.lz[x] == MINF: return
        self.t[x] = self.lz[x] * (c[rx] - c[lx])
        self.p[x] = max(0, self.t[x])
        if lx + 1 != rx:
            self.lz[2*x] = self.lz[2*x+1] = self.lz[x]
        self.lz[x] = MINF

    def upd(self, l, r, val, x, lx, rx):
        self.push(x, lx, rx)
        if lx >= r or rx <= l: return
        if lx >= l and rx <= r:
            self.lz[x] = val
            self.push(x, lx, rx)
            return
        mx = (lx + rx)//2
        self.upd(l, r, val, x*2, lx, mx)
        self.upd(l, r, val, x*2+1, mx, rx)
        self.t[x] = self.t[x*2] + self.t[x*2+1]
        self.p[x] = max(self.p[x*2], self.t[x*2] + self.p[x*2+1])

    def query(self, val, x, lx, rx):
        self.push(x, lx, rx)
        if lx + 1 == rx:
            d = self.t[x]//(c[rx] - c[lx])
            return c[lx] - 1 + val // d if self.p[x] > val else c[rx] - 1
        mx = (lx + rx)//2
        self.push(x*2, lx, mx)
        self.push(x*2 + 1, mx, rx)
        if self.p[x*2] > val:
            return self.query(val, x*2, lx, mx)
        else:
            return self.query(val - self.t[x*2], x*2+1, mx, rx)

N = int(input())
c, q = [N + 1], []

while True:
    l = input().split()
    if l[0] == "Q":
        q += [[2, int(l[1]), 0, 0]]
    elif l[0] == "I":
        q += [[1, int(l[1]), int(l[2]), int(l[3])]]
        c += [q[-1][1], q[-1][2] + 1]
    else:
        break

c = sorted(set(c))
d = {x: i for i, x in enumerate(c)}
M = len(c) - 1
MINF = -float("inf")
STree = SegmentTree(M)

for t, l, r, v in q:
    if t == 1:
        STree.upd(d[l], d[r + 1], v, 1, 0, M)
    else:
        print(STree.query(l, 1, 0, M))