시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 (추가 시간 없음) | 256 MB | 24 | 10 | 8 | 36.364% |
A new DJ is in town. DJ Darko needs to set up his speakers. He has $N$ speakers in a row with the $i$-th speaker volume set to $A_i$. Changing the volume is rather difficult so the $i$-th speaker requires $B_i$ units of energy to increase or decrease the volume by the value of $1$.
Unforutanently, Darko’s evil twin brother Karko likes to mess with him. There are $Q$ events that will be happening.
1 l r x 2 l r
In an event of type 1, Karko changes the volume of all speakers from the $l$-th to the $r$-th by $x$. In an event of type 2, Darko sets all the speakers from the $l$-th to the $r$-th to the same volume in a way that uses up the minimal amount of energy. If there are multiple ways of doing that, he chooses the one which minimizes the final volume.
As a bystander, you would like to know the volume that Darko set for each event of type 2.
The first line contains the number of speakers $N$ and the number of events $Q$. In the second line, there are $N$ numbers $A_i$ indicating the current volume of the speakers. In the third line, there are $N$ numbers $B_i$, indicating the energy needed to change the volume of the $i$-th speaker by one. In the next $Q$ lines there are $Q$ events, formatted in the way described above. All numbers in the input are integers.
For each event of type 2, output the volume to which Darko set the speakers.
5 5 8 1 6 4 9 3 6 4 1 7 2 2 4 1 1 4 -8 2 1 1 2 1 3 2 4 5
1 0 -7 9
8 3 4 3 9 3 7 6 4 8 9 5 8 5 2 2 1 8 1 1 7 -10 2 5 5 2 4 7
-3 -7
ICPC > Regionals > Europe > Central European Regional Contest > CERC 2021 D번