27179번 - Экспедиция на Сириус 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 125 | 27 | 22 | 19.469% |
문제
В компьютерную игру <<Экспедиция на Сириус>> играют $n$ игроков, пронумерованных от $1$ до $n$. За предыдущие миссии у игрока номер $i$ накоплено $c_i$ единиц опыта. Будем говорить, что два игрока имеют одинаковый уровень, если у них одинаковое значение опыта. Игрок, который имеет больше опыта, имеет более высокий уровень.
Игра состоит из нескольких раундов. В конце каждого раунда каждому игроку добавляется опыт, равный количеству различных более высоких уровней у остальных игроков. Например, если значения опыта игроков $[2, 5, 5, 1, 2, 10]$, то опыт первого игрока увеличится на 2: существует два более высоких уровня --- игроки с опытом 5 и игрок с опытом 10. Опыт последнего игрока в этом примере не увеличится. Опыт игроков изменяется одновременно. То есть в конце раунда в нашем примере опыт игроков станет равным $[4, 6, 6, 4, 4, 10]$.
Вам требуется ответить на несколько вопросов. Каждый вопрос может быть одного из трех типов:
- Сколько различных уровней будет у игроков после $k$ раундов игры?
- Какое суммарное количество единиц опыта добавится всем игрокам за первые $k$ раундов?
- Сколько единиц опыта будет у игрока номер $i$ после начисления опыта в конце $k$-го раунда?
입력
В первой строке даны два целых числа $n$ и $q$ ($1 \le n, q \le 300\,000)$ --- количество игроков и количество вопросов, на которые вам нужно ответить.
Во второй строке даны $n$ целых чисел $c_i$ ($0 \le c_i \le 10^{12}$) --- количество единиц опыта у каждого из игроков в начале текущей игры.
В следующих $q$ строках даны описания вопросов. Каждая строка начинается с целого числа $t$ ($t \in \{1, 2, 3\}$), которое обозначает тип вопроса.
- Если $t = 1$, далее дано целое число $k$ ($0 \le k \le 10^{12}$) --- количество раундов.
- Если $t = 2$, далее дано целое число $k$ ($0 \le k \le 10^{12}$) --- количество раундов.
- Если $t = 3$, далее даны два целых числа $k$ и $i$ ($0 \le k \le 10^{12}$, $1 \le i \le n$) --- количество раундов и номер игрока, опыт которого нас интересует.
Во всех вопросах $k = 0$ означает момент начала игры до проведения первого раунда.
출력
Для каждого вопроса выведите ответ на него в новой строке.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 18 | $n \le 5000$, $q \le 5000$, $c_i, k \le 10\,000$ |
| 2 | 16 | $n \le 5000$, $q \le 5000$, $c_i, k \le 10^7$ |
| 3 | 14 | $n \le 5000$, $q \le 5000$, $c_i, k \le 10^{12}$ |
| 4 | 7 | $n \le 3 \cdot 10^5$, $q \le 3 \cdot 10^5$, $c_i, k \le 10^7$ |
| 5 | 12 | $n \le 5000$, $q \le 3 \cdot 10^5$, $c_i, k \le 10^{12}$ |
| 6 | 14 | $n \le 3 \cdot 10^5$, $q \le 3 \cdot 10^5$, $c_i, k \le 10^{12}$, $t = 1$ |
| 7 | 10 | $n \le 3 \cdot 10^5$, $q \le 3 \cdot 10^5$, $c_i, k \le 10^{12}$, $t\in\{1,2\}$ |
| 8 | 9 | $n \le 3 \cdot 10^5$, $q \le 3 \cdot 10^5$, $c_i, k \le 10^{12}$ |
예제 입력 1
6 6 5 4 4 2 2 2 1 0 1 1 1 2 2 1 2 2 3 1 5
예제 출력 1
3 2 1 8 11 4
예제 입력 2
5 4 0 3 5 4 2 1 0 1 1 2 1 3 1 1
예제 출력 2
5 2 10 4
노트
В первом тесте опыт игроков изменяется следующим образом:
| Раунд | $c_1$ | $c_2$ | $c_3$ | $c_4$ | $c_5$ | $c_6$ |
|---|---|---|---|---|---|---|
| начало игры | 5 | 4 | 4 | 2 | 2 | 2 |
| 1 | 5 | 5 | 5 | 4 | 4 | 4 |
| 2 | 5 | 5 | 5 | 5 | 5 | 5 |
Во втором тесте опыт игроков изменяется следующим образом:
| Раунд | $c_1$ | $c_2$ | $c_3$ | $c_4$ | $c_5$ |
|---|---|---|---|---|---|
| начало игры | 0 | 3 | 5 | 4 | 2 |
| 1 | 4 | 5 | 5 | 5 | 5 |
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호