Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Ті, хто розв'язав задачу Conference*, можуть природним чином прийти до цієї задачі.

Вам дано рядок $S$ довжини $N$. Кожен символ рядка $S$ — це один із символів A, B, C або ?. Зокрема, перший і останній символи рядка $S$ дорівнюють A.

Для рядка довжини $N$, що складається лише із символів A, B та C, визначимо його рахунок як кількість цілих чисел $i$ ($1 \le i \le N - 1$), таких що $i$-й символ та $(i + 1)$-й символ є різними.

Вам дано $Q$ запитів. $i$-й запит має такий вигляд:

Дано невід'ємні цілі числа $X_i, Y_i, Z_i$, де $X_i + Y_i + Z_i$ дорівнює кількості символів ? у рядку $S$. Серед усіх рядків, отриманих заміною $X_i$ символів ? у $S$ на A, $Y_i$ з них — на B та $Z_i$ з них — на C, виведіть максимально можливий рахунок.

Вхідні дані

Вхідні дані подаються в такому форматі:

N
S
Q
X_1 Y_1 Z_1
X_2 Y_2 Z_2
:
X_Q Y_Q Z_Q

Вихідні дані

Виведіть $Q$ рядків. У $i$-му рядку виведіть відповідь на $i$-й запит.

Обмеження

  • $N, Q, X_i, Y_i, Z_i$ — цілі числа.
  • $2 \le N \le 3 \times 10^5$
  • $S$ — рядок довжини $N$, що складається із символів A, B, C та ?.
  • Перший і останній символи рядка $S$ дорівнюють A.
  • $1 \le Q \le 2 \times 10^5$
  • $0 \le X_i$
  • $0 \le Y_i$
  • $0 \le Z_i$
  • $X_i + Y_i + Z_i$ дорівнює кількості символів ? у рядку $S$.

Приклади

Вхідні дані 1

9
A??B??C?A
3
1 3 1
4 1 0
0 0 5

Вихідні дані 1

8
6
4

Вхідні дані 2

12
A???A?B????A
4
0 8 0
2 6 0
7 1 0
3 5 0

Вихідні дані 2

4
8
4
10

Вхідні дані 3

28
ACB??B???BCB??B????B?AAA?BBA
26
6 1 6
4 5 4
2 3 8
9 2 2
11 0 2
8 4 1
11 0 2
2 0 11
0 1 12
12 1 0
10 3 0
1 4 8
3 7 3
2 8 3
1 3 9
11 1 1
7 0 6
6 4 3
8 4 1
0 10 3
13 0 0
11 1 1
0 6 7
2 8 3
9 0 4
0 0 13

Вихідні дані 3

24
21
23
21
19
20
19
21
19
17
19
22
19
17
22
19
23
22
20
13
15
19
20
17
21
17

Примітка

У першому прикладі:

  • Для першого запиту заміна символів на ABCBABCBA дає рахунок $8$, що є максимально можливим.
  • Для другого запиту заміна символів на ABABAACAA дає рахунок $6$.
  • Для третього запиту заміна символів на ACCBCCCCA дає рахунок $4$.

* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1417EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.