Problem Statement:

Given positive integers $n$, $m$, and $m$ triplets $(l_i, r_i, c_i)$, we have an array $a_{1..n}$ initialized with zeros.

For each operation $i = 1, ..., m$, perform the following steps:

• Choose any integer $k \in [0, c_i]$.
• Add $k$ to all elements $a_j$ where $j \in [l_i, r_i]$.
• Add $c_i - k$ to all elements $a_j$ where $j \in [1, l_i) \cup (r_i, n]$.

The goal is to minimize $\max a_i$.

Approach:

This is a problem involving clever mathematical properties.

Subtask 1–2:

First, consider only the case where $c_i = 1$. This simplifies the problem into flipping certain intervals to minimize the maximum value of the resulting array. Here, flipping an interval $[l_i, r_i]$ means toggling the elements outside this range.

Let $S$ denote the set of intervals that are flipped. The key observations are:

• Property 1: Monotonicity of answer — if there exists a solution with maximum element $x$, then for any $y > x$, there also exists a solution with maximum element $y$.
• Property 2: If the union of intevrals in $S$ is empty, such a solution is not optimal.

We can use binary search on the answer. For a given threshold $x$, determine if it's feasible by checking whether there exists a subset $S$ such that all element $a_i$ do not exceed $x$ after operations.

Define:

• $p_i$: initial contribution of position $i$ when no intervals are flipped.
• $q_i$: final value at position $i$ under a particular $S$.
• $z_i$: number of intervals in $S$ that contain $i$.

Then, $q_i = p_i + |S| - 2z_i$. To ensure $q_i \leq x$, we derive: $$ z_i \geq \left\lceil \frac{p_i + |S| - x}{2} \right\rceil $$

We can fix a position $t$ in the union of intervals and iterate over $|S|$ values. Then greedily assign intervals to satisfy the lower bounds on $z_i$.

Time complexity: $O(nm(n + m)\log^2 m)$ for $c_i = 1$.

For general $c_i > 1$, let $V = \max p_i$. Time complexity becomes $O(nV(n + m)\log m \log V)$.

Here is the greedy implementation:

class Interval {
public:
    int l, r, c;

    bool operator<(const Interval& rhs) const {
        return r < rhs.r;
    }
};

std::vector<Interval> vec[maxn];

bool valid(long long x, int t, long long zt) {
    for (int i = t + 1; i <= n; i++) {
        z[i] = 0;
    }

    std::priority_queue<Interval> q;
    long long zi = 0;

    for (int i = 1; i <= t; i++) {
        long long lim = (p[i] + zt - x + 1) >> 1;

        for (int j = 0; j < vec[i].size(); j++) {
            if (vec[i][j].r > t) {
                q.push(vec[i][j]);
            }
        }

        while (!q.empty() && zi < lim) {
            Interval iter = q.top();
            q.pop();

            int delta = std::min(lim - zi, (long long)iter.c);
            zi += delta;
            z[iter.r] -= delta;

            if ((iter.c -= delta)) {
                q.push(iter);
            }
        }

        if (zi < lim) {
            return false;
        }
    }

    z[t] = zi;
    for (int i = t + 1; i <= n; i++) {
        if (((z[i] += z[i - 1]) << 1) < p[i] + zt - x) {
            return false;
        }
    }

    return true;
}

Subtask 3:

Further optimization comes from reducing the enumeration of $z_t$.

• Property 3: There exists an optimal solution where either $|S| = 0$ or $\max_{i \in I} q_i \geq \max q_i - 1$.

By adjusting the intervals in the solution, we show that the number of possible values for $z_t$ is limited. Thus, we only need to check $z_t = p_t - x$ and $z_t = p_t - x + 1$.

Time complexity reduces to $O(n(n + m)\log m \log V)$.

Subtask 4–5:

We further explore whether $t$ needs to be enumerated.

• Property 4: Let $t = \arg\max_{i \in I} q_i$. If there's an optimal solution satisfying $q_t \geq \max q_i - 1$, then $p_t = \max p_i$.
• Property 5: If there's an optimal solution with $\max_{i \in I} q_i \geq \max q_i - 1$, then all positions $x$ such that $p_x = \max p_i$ must belong to $I$.

These properties allow us to limit $t$ to indices where $p_t = \max p_i$. Then, for each such $t$, we check two cases: $z_t = p_t - x$ and $z_t = p_t - x + 1$.

Final time complexity: $O((n + m)\log m \log V)$.