페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8039

실시간 투표현황 4초 1024MB

문제

1번부터 N번까지의 후보번호를 갖는 N명의 후보자가 있다.

우리는 실시간으로 후보자 중 한 명에게 일정 개수의 표를 투표를 하는 기능과 어떤 개수의 표를 갖는 사람들의 목록을 실시간으로 알려주는 프로그램을 개발해야한다.

총 Q번의 쿼리에 대하여 아래와 같이 응답하는 프로그램을 작성하시오.


입력

첫 줄에 두 정수 N,Q가 주어진다. (2 \le N,Q \le 100,000)

두 번째 줄부터 Q줄에 걸쳐 쿼리가 주어진다.

  • 0 n k: n번 후보자에게 k표를 투표한다. (1 \le n \le N, 1 \le k \le 10,000)

  • 1 x: 현재까지 받은 표의 수가 x인 후보자를 모두 오름차순으로 출력한다. (0 \le x \le 1,000,000,000)

    • 만약 존재하지 않는다면 "None"을 출력한다.


출력

각 줄에 1\ k 형식의 쿼리가 주어지면 현재까지 받은 표의 수가 k인 후보자를 모두 오름차순으로 출력한다.

  • 모든 출력되는 횟수의 총합은 1,000,000 이하임이 보장된다.


예제1

입력
37
015
0210
15
110
13
0310
110
출력
1
2
None
23

첫 두 줄의 쿼리가 진행 된 후 각 후보자는 아래와 같은 표를 각각 갖고 있다.

1번 후보: 5표, 2번 후보: 10표, 3번 후보: 0표

여섯 번째 쿼리가 진행 된 후 상황은 아래와 같다.

1번 후보: 5표, 2번 후보: 10표, 3번 후보: 10표


태그

출처

@klee

역링크