結果
| 問題 |
No.2361 Many String Compare Queries
|
| ユーザー |
 gew1fw
|
| 提出日時 | 2025-06-12 17:01:55 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,646 bytes |
| コンパイル時間 | 197 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 69,888 KB |
| 最終ジャッジ日時 | 2025-06-12 17:02:08 |
| 合計ジャッジ時間 | 4,866 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 4 WA * 2 TLE * 1 -- * 7 |
ソースコード
import sys
from collections import deque
class State:
def __init__(self):
self.next = {}
self.link = -1
self.len = 0
self.count = 0
self.sum_pos = 0
self.transitions = {} # to store transitions and their count and sum_pos
class SuffixAutomaton:
def __init__(self):
self.size = 1
self.last = 0
self.states = [State()]
def sa_extend(self, c, pos):
p = self.last
curr = self.size
self.size += 1
self.states.append(State())
self.states[curr].len = self.states[p].len + 1
self.states[curr].sum_pos = pos
self.states[curr].count = 1
while p >= 0 and c not in self.states[p].next:
self.states[p].next[c] = curr
p = self.states[p].link
if p == -1:
self.states[curr].link = 0
else:
q = self.states[p].next[c]
if self.states[p].len + 1 == self.states[q].len:
self.states[curr].link = q
else:
clone = self.size
self.size += 1
self.states.append(State())
self.states[clone].len = self.states[p].len + 1
self.states[clone].next = self.states[q].next.copy()
self.states[clone].link = self.states[q].link
self.states[clone].count = 0
self.states[clone].sum_pos = 0
while p >= 0 and self.states[p].next.get(c, -1) == q:
self.states[p].next[c] = clone
p = self.states[p].link
self.states[q].link = clone
self.states[curr].link = clone
self.last = curr
def compute_count_sum(self):
# We need to process states in order of decreasing length and accumulate counts and sums
# Using a topological order (based on length)
states_order = sorted(range(self.size), key=lambda x: -self.states[x].len)
for state in states_order:
if self.states[state].link != -1 and self.states[state].link != 0:
self.states[self.states[state].link].count += self.states[state].count
self.states[self.states[state].link].sum_pos += self.states[state].sum_pos
def main():
import sys
input = sys.stdin.read
data = input().split()
idx = 0
N = int(data[idx])
idx +=1
Q = int(data[idx])
idx +=1
S = data[idx]
idx +=1
# Build the suffix automaton
sam = SuffixAutomaton()
for i in range(N):
c = S[i]
sam.sa_extend(c, i+1) # assuming 1-based positions
sam.compute_count_sum()
# Now, preprocess for each state, the transitions and their count and sum_pos
for state_idx in range(sam.size):
state = sam.states[state_idx]
for c, next_state_idx in state.next.items():
state.transitions[c] = (sam.states[next_state_idx].count, sam.states[next_state_idx].sum_pos)
for _ in range(Q):
L = int(data[idx])
idx +=1
R = int(data[idx])
idx +=1
T = S[L-1:R] # since S is 0-based, L and R are 1-based as per input
m = len(T)
# Compute part1
part1 = 0
current_state = 0
valid = True
for k in range(m-1):
c = T[k]
if c in sam.states[current_state].next:
current_state = sam.states[current_state].next[c]
part1 += sam.states[current_state].count
else:
valid = False
break
if not valid:
part1 = 0
# Compute part2
part2 = 0
current_state = 0 # start with the initial state for k=1
# For k=1
sum_count = 0
sum_pos = 0
for c in 'abcdefghijklmnopqrstuvwxyz':
if c < T[0]:
if c in sam.states[0].next:
next_state = sam.states[0].next[c]
cnt = sam.states[next_state].count
sum_p = sam.states[next_state].sum_pos
sum_count += cnt
sum_pos += sum_p
contribution = sum_count * (N + 1) - sum_pos
part2 += contribution
# Now for k >=2
current_state = 0 # reset to initial state
for k in range(1, m):
c = T[k]
# Check if current_state can transition to the next character to form the prefix of length k
# Wait, for k>=2, the prefix is T[0..k-1], so for each step, we need to find the state after T[0..k-2]
# So, we need to track the state after each k-1
# Thus, for each k, after processing k-1, the state is T[0..k-2]
# So, let's process each k and track the state for T[0..k-1]
# But for k=1, T[0..k-1] is empty, which is the initial state
# So, for this approach, we need to track the state after each k-1
# So, for k from 1 to m, the state for T[0..k-1] is current_state
# So, for k=1, current_state is the initial state
# For k=2, current_state is for T[0], and so on.
# So, after processing k=1, current_state is for T[0], which is needed for k=2
# But in our approach, for each k, we need to find the state for T[0..k-1], which is current_state
# So, for k=1, current_state is initial state
# For k=2, current_state is for T[0]
# And so on.
# So, for each k, after processing, current_state is updated to T[0..k-1]
# Thus, for the next k+1, it's for T[0..k]
# So, the code should process each k step by step, updating current_state for the next k.
# But in this case, for part2, we need the state for T[0..k-1] for k>=1, which is current_state.
# Thus, the code for part2 is as follows:
# For k from 1 to m:
# find the state for T[0..k-1] (current_state)
# for c < T[k], if current_state has transition to c, add the contribution
# then, try to update current_state to T[0..k], for the next k.
# But for part2, after processing k, we can proceed to the next k.
# So, the code should first process part2 for k=1, then k=2, and so on.
# However, due to the complexity, perhaps the code can be structured as follows:
# For each k from 1 to m:
# find the state for T[0..k-1]
# process part2 for this k
# then, try to find the state for T[0..k]
# So, after processing part2 for k=1, we can find the state for k=2, and so on.
# Thus, the code can be written as:
# current_state = 0 # initial state for k=0 (empty string)
# for k in 1..m:
# process part2 for k using current_state (which is for T[0..k-1])
# try to find the state for T[0..k] to proceed to the next iteration
# So, for k=1:
# current_state is 0 (empty string)
# process part2 for k=1
# then try to move to k=2, which is T[0..1]
# if current_state can transition with T[0], set current_state = next state
# else, break
# So, we need to process each k step by step and update current_state for the next k.
# Thus, the code should be modified to handle this.
# However, due to time constraints, I'll proceed with the initial approach, which may not be optimal.
print(part1 + part2)
if __name__ == "__main__":
main()