Powers of Two

면접 대비

시간 제한1초메모리 제한2048 MB

요약

N = 0에서 시작해 2^x를 더하거나 빼는 질의를 Q번 처리하면서, 각 질의 후 N이 0이 되는지 판정한다.

난이도: 보통10점 중 6점
유형: 비트 연산, 구현, 수학, 해시맵
정답자: 아직 제출이 없습니다

문제

Adrian has learned addition and subtraction from Morgan and is now ready to learn a new concept, the powers of two. Powers of two are integers in the form of $2^x$ , where $x ≥ 0$ . Some examples of powers of two are $1, 2, 4, 8, \dots$ .

To ensure Adrian understands this new concept, Morgan prepares a challenge for him. At first, Adrian is given an integer $N = 0$ . Then, Morgan will give him $Q$ queries. Each query can be one of the following types:

+ $x$ , which will add the value of $N$ by $2^x$ , or
- $x$ , which will subtract the value of $N$ by $2^x$ .

Adrian is instructed to clap his hands whenever $N$ becomes $0$ after each query.

Adrian finds this challenge is very hard to follow. He asks you whether he should clap or not after each query.

입력

Input begins with an integer $Q$ ( $1 ≤ Q ≤ 200\\, 000$ ) representing the number of queries. Each of the next $Q$ lines contains a character and an integer $T$ $x$ ( $T ∈ \\{$ +, - $\\}$ ; $0 ≤ x ≤ 200\\, 000$ ) representing the query.

출력

After each query, output YES in a single line if the value of $N$ becomes $0$ , or output NO otherwise.

예제2

예제 1

입력

6
+ 3
+ 3
- 4
- 6
+ 7
- 6

예상 출력

NO
NO
YES
NO
NO
YES

예제 2

입력

예상 출력

NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES