912 . SALAD 沙啦

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

omelet

User's AC Ratio

94.1% (16/17)

Submission's AC Ratio

50.0% (23/46)

Tags

ioicamp ioicamp-2025

Description

你吃喜歡吃沙拉嗎？

沙拉是一種把各項生鮮食材和特殊的醬料拌在一起，能一口品嚐到不同健康風味的料理。

🥗🥗🥗🥗🥗🥗🥗🥗🥗🥗

巴乙己也喜歡吃沙拉。
巴乙己最喜歡的沙拉裡有 $N$ 種食材，
第 $i$ 種食材可以用一個字串 $s_i$ 表示。

巴乙己吃沙拉時不喜歡太複雜的味道。
他總共會吃 $Q$ 口沙拉，
第 $j$ 口只會（用手）拿起兩種食材 $a_j$ 和 $b_j$，
並從第 $a_j$ 種食材的第 $x_j$ 個位置和第 $b_j$ 種食材的第 $y_j$ 個位置咬下。

巴乙己喜歡大口吃沙拉。
第 $j$ 口的大小可以表示為一個整數 $l_j$，
代表他咬下了第 $a_j$ 種食材的 $[x_j, x_j + l_j)$
和第 $b_j$ 種食材的 $[y_j, y_j + l_j)$。
為了不要使一口的味道太複雜，
他需要保證 $s_{a_j}[x_j, x_j + l_j) = s_{b_j}[y_j, y_j + l_j)$，
同時吃到最大口，也就是要最大化 $l_j$。

現在，給你他每一口沙拉的計劃，
請你求出他每一口最大可以是多大吧！

Input Format

輸入第一行有兩個正整數 $N, Q$，意義如題敘所述。

接下來有 $N$ 行，第 $i$ 行有一個字串 $s_i$。

接下來有 $Q$ 行，第 $j$ 行有四個非負整數 $a_j, b_j, x_j, y_j$。

  • $1 \le N \le 10 ^ 6$
  • $1 \le |s_i| \le 10 ^ 6, \sum |s_i| \le 10 ^ 6$
  • $1 \le Q \le 5 \times 10 ^ 6$
  • $0 \le a_j < N, 0 \le b_j < N$
  • $0 \le x_j < |s_{a_j}|, 0 \le y_j < |s_{b_j}|$
  • $(a_j, x_j) \ne (b_j, y_j)$
  • 所有的 $s$ 僅包含大寫英文字母

Output Format

請輸出一個整數 $L = \sum_{j = 0} ^ {Q - 1} l_j \cdot p ^ {Q - 1 - j} \bmod M$，
其中 $p = 989,898,989, M = 1,234,567,891$。

Sample Input 1

1 10
ABAABAAAB
0 0 5 6
0 0 6 2
0 0 2 7
0 0 7 3
0 0 3 0
0 0 0 8
0 0 8 4
0 0 4 1
0 0 3 6
0 0 8 1

Sample Output 1

208276969

Sample Input 2

3 2
NTUCPC
CPC
CPIOIAM
0 1 3 0
1 2 0 0

Sample Output 2

500561187

Hints

沙拉怎麼可以少了醬料？

範例輸入第一筆未雜湊的輸出為

0: 2
1: 3
2: 1
3: 2
4: 4
5: 0
6: 1
7: 3
8: 1
9: 1

第二筆的輸出為

0: 3
1: 2

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~5, 10~13 $N = 1$ 22
3 0~1, 10~16 $Q \le 10 ^ 6$ 33
4 0~16 無額外限制 45

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 1048576 65536 1 3 4
1 5000 1048576 65536 1 3 4
2 5000 1048576 65536 2 4
3 5000 1048576 65536 2 4
4 5000 1048576 65536 2 4
5 5000 1048576 65536 2 4
6 5000 1048576 65536 4
7 5000 1048576 65536 4
8 5000 1048576 65536 4
9 5000 1048576 65536 4
10 5000 1048576 65536 2 3 4
11 5000 1048576 65536 2 3 4
12 5000 1048576 65536 2 3 4
13 5000 1048576 65536 2 3 4
14 5000 1048576 65536 3 4
15 5000 1048576 65536 3 4
16 5000 1048576 65536 3 4
Submit
Back to Top