시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1929 | 724 | 314 | 30.604% |
어려서부터 땅따먹기를 곧잘 즐기던 구사과는, 땅따먹기로 입신의 경지에 다다르게 되었다. 그래서 구사과는 자신만이 할 수 있는 새로운 땅따먹기 게임을 만들었는데, 이름하여 반평면 땅따먹기이다.
반평면 땅따먹기의 규칙은 땅따먹기보다 좀 더 간단하다. 땅따먹기 특이점을 넘긴 능력을 보유한 구사과는 땅따먹기에서만큼은 뭐든지 할 수 있다. 이를테면 무한히 먼 곳으로부터 손가락으로 돌을 쳐 무한히 멀리 직선으로 날아가도록 할 수 있다. 반평면 땅따먹기는 이 능력을 이용한 게임으로, 구사과가 점령하는 돌을 쳐서 날릴 때마다 그 자취인 직선을 기준으로 나뉘는 두 영역 중 (0, -∞)를 포함하는 쪽 전부를 점령하게 된다.
무한한 2차원 평면 위에서 게임을 하던 구사과는 문득 현재 자신이 점령한 땅의 모양에 관해서 궁금해졌다. 하지만 땅따먹기 이외에는 젬병인 구사과는 정작 자신이 점령한 땅에 대해서는 잘 알지 못했다. 높은 곳을 좋아하는 구사과는 종종 자신이 점령한 땅 중 해당 x좌표에서 가장 높은 y좌표가 몇인지 알고 싶었다.
우수한 프로그래머인 당신만이 구사과의 유일한 희망이다. 구사과가 게임을 진행한 정보가 주어질 때 이를 토대로 구사과의 궁금증을 해결해주자!
첫 줄에는 게임을 진행한 정보의 개수 Q(1 ≤ Q ≤ 200,000)이 주어지며, 이어서 Q 줄에 걸쳐 각 정보가 주어진다. 각 줄의 첫 번째 숫자가 1일 경우 이어서 2개의 정수 a, b(|a| ≤ 1,000,000, |b| ≤ 1,000,000,000,000)가 주어지며 이는 구사과가 y = ax + b 형태의 직선을 따라 돌을 날렸음을 의미한다. 각 줄의 첫 번째 숫자가 2일 경우 이어서 1개의 정수 x(|x| ≤ 1,000,000,000,000)이 주어지며, 이는 구사과가 현재까지 점령한 땅 중 해당 x 좌표에서 가장 높은 y값을 궁금해함을 의미한다. 첫 번째 정보는 무조건 1로 시작함이 보장된다.
모든 구사과의 궁금증에 대하여 해당하는 y값을 한 줄에 걸쳐 하나씩 출력한다.
4 1 1 2 1 2 3 2 -100 2 100
-98 203