입주 회사 최고 자산
시간 제한5초메모리 제한128 MB
회사가 사무실에 입주하면 시간에 따라 선형으로 재산이 변하는 상황에서, 구간 내 최고 재산을 질의마다 구해야 하는 문제입니다.
문제
사무실이 N개 있고, 왼쪽부터 오른쪽까지 1번부터 N번까지 번호가 붙어 있다. 처음에는 모든 사무실이 비어 있다.
회사가 입주할 때는 다음 정보가 주어진다.
- T: 입주일. 사업을 시작한 날을 1일로 센다.
- K: 입주할 사무실 번호
- Z: 하루에 벌거나 잃는 금액. 손해를 보는 회사라면 음수일 수 있다.
- S: 입주일 당시 회사가 가진 금액
이미 회사가 있는 사무실 K에 새 회사가 입주하면, 기존 회사는 그날 사무실을 비운다. 입주하는 날에는 하루 종일 이사를 하므로 그날의 수익은 발생하지 않는다. 그 뒤로 회사가 사무실에 머무르는 동안에는 매일 업무가 끝난 뒤 가진 금액이 정확히 Z만큼 변한다. 따라서 T0일에 S를 가지고 입주한 회사가 D일 업무 종료 후에도 같은 사무실에 있다면, 그 회사의 금액은 S + (D - T0) × Z이다.
가끔 어느 구간에서 가장 부유한 회사가 어디인지 조사한다. 조사는 두 사무실 A와 B를 끝점으로 하는 연속 구간 전체를 대상으로 하며, A가 B보다 클 수도 있다. 조사는 항상 그날 입주한 회사들의 업무가 모두 끝난 뒤에 이루어진다.
입주 이벤트와 조사 이벤트가 시간순으로 주어질 때, 각 조사에 대한 답을 구하라.
입력
첫째 줄에 사무실의 개수 N과 이벤트의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000)
다음 M개 줄에는 이벤트가 시간순으로 주어진다.
- 회사 입주: 1 T K Z S
- 조사: 2 T A B
하루에 일어나는 이벤트는 최대 한 개이므로, 입력의 T는 항상 증가한다. 마지막 이벤트가 일어난 날은 1,000,000보다 작다. |Z|와 |S|도 각각 1,000,000보다 작다.
출력
각 조사마다, 조사 구간에 있는 회사 중 가장 많은 금액을 가진 회사의 금액을 한 줄에 하나씩 출력한다. 조사 구간에 입주한 회사가 하나도 없다면 nema를 출력한다.