Inspektor
레이팅 미적용의견: 0
\(2^{nd}\) round, November \(10^{th}\), 2012
A new town was just inaugurated in a small country. As usual, Mirko has secured the position of the
chief tax inspector. His duty is ensuring adequate accounting in all the different companies in the town.
There are N business offices along the main street, numbered 1 to N from left to right. All offices are
empty in the beginning; in time, companies will move in and out of these offices. From time to time,
Mirko will pass by some of the offices and inspect the accounting of only one company, the currently
wealthiest one in those offices.
A company moving in is described by four integers:
T – the mo\(ve-in\) day, numbered from town inauguration (which is day 1),
K – the office number,
Z – the daily profit of the company (can be negative if the company is losing money),
S – balance of the company's account on mo\(ve-in\) day.
If there is already a company in office K, that company moves out when the new company moves in.
The new company doesn't open for business (or earn profit) until the day after mo\(ve-in\).
Mirko's inspection stroll is described by three integers:
T – the inspection day, numbered from town inauguration,
A and B – Mirko will pass by all offices with numbers between A and B, inclusive.
Since Mirko works only at the end of the day, all companies will have already finished business and
posted profit for the day by the time of Mirko's stroll.
Help Mirko by writing a program to find, for each stroll, the account balance of the currently wealthiest
company that Mirko is passing by.
The first line of input contains two positive integers, N (\(1 \le N \le 100\,000\)) and M (\(1 \le M \le 300\,000\)),
the number of offices and events, respectively.
Each of the following M lines contains a description of one event, formatted either as “1 T K Z S” (for
company mo\(ve-in\)) or as “2 T A B” (for Mirko's inspection stroll).
All events are given chronologically, and at most one event will happen each day (that is, T will be
strictly increasing). The last event's day number will be less than \(10^{6}\), and all Z and S numbers' absolute
values will be less than \(10^{6}\).
\(2^{nd}\) round, November \(10^{th}\), 2012
For each Mirko's stroll output a line containing the account balance of the company that Mirko will
inspect, or the word “nema” (without quotes) if all offices that he will pass by are empty.
2 4
1 1 1 2 4
1 2 2 3 2
2 5 1 2
2 7 1 212
173 6
1 1 1 4 -2
1 2 2 2 6
2 3 3 1
2 4 3 1
1 5 3 -6 20
2 6 2 38
10
145 9
1 1 5 4 -5
2 2 3 5
1 3 4 6 9
2 4 1 2
1 6 2 2 3
2 8 2 1
1 9 4 0 17
2 10 5 5
2 11 1 4-1
nema
7
31
17평가 및 의견
Inspektor
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Inspektor