시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 2316 | 481 | 224 | 17.297% |
UCPC 2015년도 우승자 범수, 상수 형제는 가끔 배열을 가지고 논다. 이들은 크기 N인 배열 A=[a1,…,aN]을 가지고 있다. 처음에는 모든 i(1≤i≤N)에 대해 ai=i이다. 이 형제들은 Q개의 질의를 받아 순서대로 해결하면서 논다. 질의는 다음과 같은 네 종류 중 하나이다.
[a1,…al-1,ar,ar-1,…,al+1,al,ar+1,…,aN]
[a1,…al-1,ar-x+1,…,ar-1,ar,al,al+1,…,ar-x,ar+1,…,aN]
하나의 질의를 수행한 다음 배열이 바뀌고 나면, 그 결과는 다음의 질의에도 영향을 미친다. 이때, 범수, 상수 형제가 질의를 해결할 때마다 구한 값을 출력하고, 모든 질의를 해결한 뒤 마지막 배열의 모습을 출력하라.
입력의 첫 줄에는 배열의 크기를 나타내는 자연수 N과 질의의 수를 나타내는 자연수 Q가 주어진다.(1 ≤ N, Q ≤ 300,000) 그 다음 Q개의 줄에 걸쳐 각 질의의 정보가 네 종류 중 하나의 형식으로 주어진다.
Q개의 줄에 걸쳐 각 질의마다 구해야 하는 값을 공백으로 구분하여 한 줄씩 출력한다. 1번과 2번 질의는 최솟값, 최댓값, 합 순서로 출력하고, 3번과 4번 질의는 구하는 값 하나를 출력한다. 마지막 (Q+1)번째 줄에는 모든 질의를 해결한 후 배열의 값을 공백으로 구분하여 한 줄에 출력한다.
5 5 1 2 4 3 4 2 3 5 1 2 1 3 -2 4 3
2 4 9 2 2 5 10 1 5 10 4 5 1 4 3 2
[1, 2, 3, 4, 5]→[1, 4, 3, 2, 5]→[1, 4, 5, 3, 2]→[5, 1, 4, 3, 2]
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2016 A번