P8300 [COCI 2012/2013 #2] INSPEKTOR

**The score of this problem follows the original COCI setting, with a full score of $160$.**

A new town has just been built in a small country. As usual, Mirko got the job of chief tax inspector. His duty is to ensure proper accounting for all the different companies in the town. Along the main street there are $N$ offices, numbered from left to right as $1 \sim N$. At the beginning, all offices are empty. Over time, companies will move in and out of these offices. From time to time, Mirko will walk past some offices and only check the currently richest company among those offices. A company moving in is described by four integers: - $T$: the day it moves in. The day the town is built is defined as day $1$. - $K$: the office index. - $Z$: the company’s daily profit (can be negative if the company is losing money). - $S$: the company’s account balance on the day it moves in. If there is already a company in office $K$, then when the new company moves in, the old company moves out. The new company does not start operating (earning profit) until the second day after it moves in. Mirko’s inspection walk is described by three integers: - $T$: the day of the walk. The day the town is built is defined as day $1$. - $A, B$: Mirko will pass by all offices in $[A, B]$. Because Mirko only works at the end of the day, when he walks, all companies have already finished their business for that day and reported that day’s profit. Help Mirko write a program that, for each walk, finds the account balance of the currently richest company among the offices he passes.

The first line contains two positive integers, $N\ (1 \le N \le 10^5)$ and $M\ (1 \le M \le 3 \times 10^5)$, representing the number of offices and the number of events. The next $M$ lines each contain one event description, in the format `1 T K Z S` (a company moves in) or `2 T A B` (Mirko’s walk). All events are given in chronological order, and at most one event happens per day (that is, $T$ is strictly increasing). The day of the last event is less than $10^6$. The absolute values of all $Z$ and $S$ numbers are less than $10^6$.

For each of Mirko’s walks, output one line containing the account balance of the company Mirko inspects, or the word `nema` if all offices he passes are empty.

Translated by ChatGPT 5