시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 14 9 7 63.636%

문제

원소가 하나도 없는 공집합 상태의 정수 쌍들(pairs of integers) 집합이 있을 때에, n개의 연산이 주어집니다. 각 연산은 세 가지 유형 중 하나입니다.

  1. 정수 쌍 (a, b)를 집합에 추가
  2. i번째 연산에서 추가했던 정수 쌍을 집합에서 제거
  3. 주어지는 정수 x에 대하여 집합에 남아있는 모든 원소 (a, b) 중 ax+b의 최댓값을 출력

주어진 연산을 수행하는 프로그램을 작성하세요.

입력

첫째 줄에 연산의 개수를 나타내는 n 이 주어집니다. (1≤n≤300,000)

둘째 줄부터 n개의 줄은 연산의 종류를 알려주는 하나의 정수 Type(1, 2, 3 중 하나)으로 시작한다.

Type이 1이라면, 연산 1에 해당하는 2개의 정수 a, b가 주어진다. (-109≤a, b≤109)

Type이 2라면, 연산 2에 해당하는 1개의 정수 i(1≤i≤n)가 주어진다. I는 해당 연산의 번호보다 작음이 보장되고, i번째 연산은 1번 연산이며 해당 연산으로 추가된 정수 쌍은 이전에 또 제거된 적이 없음도 보장된다.

Type이 3이라면, 연산 3에 해당하는 1개의 정수 x가 주어진다. (-109≤x≤109)

출력

연산 3을 수행할 때마다의 답을 순서대로 한 줄에 하나씩 출력합니다. 만약 정수 쌍들의 집합이 공집합이라면 “EMPTY”를 출력합니다. (따움표 제외)

예제 입력 1

7
3 1
1 2 3
3 1
1 -1 100
3 1
2 4
3 1

예제 출력 1

EMPTY
5
99
5

출처

  • 문제의 오타를 찾은 사람: bupjae