시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
13 초 | 230 MB | 316 | 39 | 31 | 19.872% |
두 사람 바자(Bazza)와 샤자(Shazza)가 다음 게임을 하고 있다. 게임판은 셀로 이루어진 그리드로 되어 있고, R 개의 행이 차례로 번호가 0, …, R - 1 로 매겨져 있고 C 개의 열이 차례로 번호가 0, …, C - 1 로 매겨져 있다. (P, Q) 는 행 P , 열 Q 에 있는 셀을 나타낸다. 각 셀에는 음이 아닌 정수가 쓰여 있고, 게임이 시작될 때 모든 셀의 값은 0이다.
이 게임은 다음과 같이 진행된다. 게임 진행 중에, 바자는 다음 두 가지 중 하나를 할 수 있다.
바자는 최대 NU + NQ 번 위와 같은 일을 (셀의 값을 NU 번 업데이트하고 NQ 번 질의을 함) 한 다음에는 지루해서 크리켓을 하러 간다.
당신의 임무는 정답을 구하는 것이다.
R = 2 이고 C = 3 이라고 하고, 바자가 다음과 같이 업데이트를 한다고 하자.
이 결과는 위 그림과 같다. 그리고 바자는 다음 직사각형에 대해 최대공약수가 무엇인지 질의한다.
바자가 다음과 같이 업데이트를 했다고 하자
새로운 그리드는 위 그림과 같다. 그리고, 바자는 다음 직사각형에 대해서 다시 최대공약수 GCD 를 질의한다.
여기까지 바자가 한 업데이트는 NU = 5 회, 질의는 NQ = 4 회이다.
첫째 줄에 행의 개수 R, 열의 개수 C, 일의 개수 N이 주어진다. (1 ≤ R, C ≤ 109)
다음 N개 줄에는 일이 발생하는 순서대로 한 줄마다 일 하나씩 주어진다. (NU ≤ 22,000, NQ ≤ 250,000)
바자가 어떤 셀의 숫자를 바꾸는 일은 1 P Q K로 주어진다. (0 ≤ P ≤ R-1, 0 ≤ Q ≤ C-1, 0 ≤ K ≤ 1018)
어떤 직사각형 내의 최대공약수를 구하는 일은 2 P Q U V로 주어진다. (0 ≤ P ≤ U ≤ R-1, 0 ≤ Q ≤ V ≤ C-1) (P, Q)와 (U, V)를 모퉁이로 하는 직사각형 내에 포함된 모든 숫자들의 최대공약수를 계산하여야 한다. 이 직사각형의 범위는 테두리를 포함한다. 즉, (P, Q) 와 (U, V) 가 포함되어 있어야 한다.
직사각형 범위 내에 모든 숫자가 0인 경우에는, 최대공약수는 0이다.
직사각형 내의 모든 숫자들의 최대공약수를 일이 주어질 때 마다, 최대공약수를 한 줄에 하나씩 순서대로 출력한다.
2 3 9 1 0 0 20 1 0 2 15 1 1 1 12 2 0 0 0 2 2 0 0 1 1 1 0 1 6 1 1 1 14 2 0 0 0 2 2 0 0 1 1
5 4 1 2
Olympiad > International Olympiad in Informatics > IOI 2013 > Day 2 6번 (수정)