JOI Spring Camp 2016 Day 3- 회전초밥 > 문제은행 : 정보올림피아드&알고리즘


4783 : 회전초밥

제한시간
12000 ms   
메모리제한
512 MB   
해결횟수
0 회   
시도횟수
1 회   

문제

회전초밥전문점 준혁초밥은 초밥을 담은 접시를 원모양의 컨베이어 벨트로 운반하고 있다.

컨베이어 벨트는 반시계방향으로 돌고 있다.

현재, 가게 내에는 손님 1부터 손님 N까지 N명의 손님이 있고, 손님은 컨베이어 벨트에 시계 반대방향으로 앉아있다.

손님 N옆에는 손님 1이 앉아있다.

 

손님은, 한 사람이 한 개씩 접시를 갖고 있다.

각 접시에는 가치라고 불리는 숫자가 정해져 있어서, 가게를 나갈 때에 손님은 자신이 가지고 있는 접시의 가치와 같은 양의 돈을 지불한다.

준혁초밥에서는 색다른 타임 세일을 하고 있다.

이 타임세일에는, Q번에 나누어 차례대로 요리사로부터 접시가 제공된다.

i(1 ≤ i ≤ Q)번째 접시의 내용은 3개의 수 (Si, Ti, Pi)로 표시된다.

 

타임세일의 룰은 다음과 같다.

타임 세일이 시작하기 직전, 초밥장인 준혁이는 컨베이어 벨트에 있는 접시를 모두 회수한다.

그 후, 아래의 과정을 i = 1, 2, ... , Q까지 반복한다.

 

1. 준혁이가 손님 Si 앞 위치 컨베이어 벨트에 가치 Pi의 접시를 놓는다.

2. 접시는 손님 Si의 위치부터 손님 Ti의 위치 까지 컨베이어 벨트 위를 이동한다.

각각의 손님은 자신의 앞의 접시에 대해 다음 행동을 한다.

- 만약, 그 접시의 가치가 자신이 갖고 있는 접시의 가치보다 작으면, 자신의 접시와 컨베이어 벨트의 접시를 교환한다.

- 만약, 그 접시의 가치가 자신이 갖고 있는 접시의 가치 이상이면, 접시를 교환하지 않는다.

3. 접시가 Ti에 도착한 후, 준혁이가 그 접시를 회수한다.

 

당신은 준혁이 밑에서 장인수업을 듣고 있는 제자이고, 가게 접시의 설거지를 맡고 있다.

접시의 가치에 따라 설거지 방법이 다르다.

당신은 설거지를 준비하기 위해서, 타임세일 Q번에 대해 준혁이가 어떤 가치의 접시를 회수하는지 알고 싶다.

각각의 손님이 타임세일 직전에 가지고 있는 접시의 정보와 타임세일에 제공될 접시의 정보가 주어졌을 때, 준혁이가 회수하는 각 접시의 가치를 구하는 프로그램을 작성하라.​

 

[부분문제]

Subtask #1 : N, Q ≤ 2 000

Subtask #2 : Si = 1, Ti = N

Subtask #3 : 문제의 조건 외에 주어진 제한이 없다.​ 


입력형식

첫째 줄에는 정수 N, Q가 공백으로 구분되어 들어온다.

이는 손님의 수가 N명이며, 타임세일에 제공될 접시의 수가 Q개 라는 것을 의미한다.

다음 N개의 줄의 i번째 줄(1 ≤ i ≤ N)에는 정수 Xi가 입력으로 들어온다.

이는 손님 i가 타임세일 직전에 가치 Xi의 접시를 가지고 있다는 것을 의미한다.

다음 Q개의 줄의 i번째 줄에는 정수 Si, Ti, Pi가 공백으로 구분되어 들어온다.

이는, i번째 제공되는 접시가 (Si, Ti, Pi)로 표시됨을 의미한다​. 

 

- 1 ≤ N ≤ 400 000

- 1 ≤ Q ≤ 25 000

- 1 ≤ Xi ≤ 1 000 000 000 (1 ≤ i ≤ N)

- 1 ≤ Si ≤ N (1 ≤ i ≤ Q)

- 1 ≤ Ti ≤ N (1 ≤ i ≤ Q)

- 1 ≤ Oi ≤ 1 000 000 000 (1 ≤ i ≤ Q)​ 


출력형식

i번째 줄 (1 ≤ i ≤ Q)에, i번째로 준혁이가 회수하는 접시의 가치를 의미하는 정수를 출력하여라. 


입력 예

6 7
8
6
7
4
5
9
2 4 5
4 1 4
6 2 7
1 5 2
3 4 8
4 3 1
3 1 3

출력 예

7
9
8
7
8
6
5

입력 예

4 2
5
2
4
7
1 4 3
1 4 1

출력 예

7
5

입력 예

10 10
19
5
8
17
14
3
9
10
7
6
1 8 4
7 3 2
5 9 10
4 8 3
10 3 6
8 7 4
6 6 3
2 9 12
6 3 7
9 6 3

출력 예

19
10
14
17
8
10
3
12
7
9


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP