cho.sh의리 게임
아직 제출이 없습니다시간 제한2초메모리 제한1024 MB문제 설명
예제1
문제
의리 게임이란 주어진 X 리터의 술을 1번부터 N번까지 번호가 붙여진 학생 N 명이 차례대로 모두 마셔야 하는 게임이다. 다행히 항공대학교 학생들은 모두 의리가 넘쳐서 자신에게 넘어온 술은 최대 주량까지 마시려고 노력한다.
여기서 최대 주량이란 어떤 사람이 마실 수 있는 술의 최대량을 의미한다. 만약 술을 한계까지 모두 마시게 되면 만취 상태가 되며 그때부터는 의리를 잊고 다음 번호의 학생에게 술을 바로 넘겨버린다. 단, 마지막 차례의 학생에게 술이 왔을 때 술을 마시다 만취 상태가 되거나 이미 만취 상태라면 술을 모두 버리게 된다.
이때 다음과 같은 두 가지 질의가 시간 순서대로 주어진다. 이 질의는 누적된다.
- 1 i x: i 번 사람이 x 리터의 술을 가지고, i번 사람부터 시작하여 N번 사람까지의 의리 게임을 진행한다. (1≤i≤N; 1≤x≤1,000,000,000)
- 2 i: 지금까지 i 번 학생이 마신 술의 양을 출력한다. (1≤i≤N)
주어지는 질의를 올바르게 처리해 보자.
입력
첫째 줄에 사람의 수 N, 질의의 수 Q 가 공백으로 구분되어 주어진다. (1≤N,Q≤100,000)
둘째 줄부터 N개의 줄에 걸쳐 i번 학생의 최대 주량 m_i가 주어진다. (1≤m_i≤109; 1≤i≤N)
N+2째 줄부터 Q 개의 줄에 걸쳐 각 질의가 위에서 설명한 형식대로 주어진다.
주어지는 수는 모두 정수이다.
출력
2번 질의에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.