結果
| 問題 |
No.284 門松と魔法(2)
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:10:43 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,664 bytes |
| コンパイル時間 | 419 ms |
| コンパイル使用メモリ | 82,688 KB |
| 実行使用メモリ | 181,420 KB |
| 最終ジャッジ日時 | 2025-05-14 13:12:13 |
| 合計ジャッジ時間 | 10,297 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 23 TLE * 1 -- * 16 |
ソースコード
import sys
# Set higher recursion depth for safety, though iterative segment tree should be fine.
# sys.setrecursionlimit(200000)
def solve():
N = int(sys.stdin.readline())
# Handle cases where N is too small to form a valid sequence of length >= 3.
# The problem defines valid sequences as M=0 or M>=3 satisfying conditions.
# Any sequence of length 1 or 2 is not valid according to this problem statement structure.
# Thus, if N <= 2, the maximum possible valid length is 0.
if N <= 2:
# Consume the second line (array elements) if N > 0, as it's provided but not needed.
if N > 0:
sys.stdin.readline()
print(0)
return
# Read the bamboo heights
A = list(map(int, sys.stdin.readline().split()))
# Coordinate compression: Map original heights to ranks [0, D-1]
# This is useful for using data structures like segment trees where array indices are needed.
# Get unique sorted values
coords = sorted(list(set(A)))
# Create a dictionary mapping each height to its rank
rank = {val: i for i, val in enumerate(coords)}
# D is the number of distinct heights
D = len(coords)
# Segment Tree Implementation
# Supports Range Maximum Query and Point Update operations.
# Uses an iterative approach for potentially better performance and avoiding deep recursion.
class SegmentTree:
def __init__(self, size):
# Calculate the smallest power of 2 greater than or equal to size for the tree array
self.actual_size = 1
while self.actual_size < size:
self.actual_size <<= 1
# Initialize data array with 0s. Array size is 2 * power_of_2.
self.data = [0] * (2 * self.actual_size)
# Update leaf k (0-indexed) with value x.
# This update assumes we want to store the maximum length found so far for this state.
# So we only update if the new value x is greater than the existing value.
def update(self, k, x):
# Map k to the leaf index in the segment tree array
k += self.actual_size
# Optimization: If the new value is not greater, no update needed.
if x <= self.data[k]:
return
self.data[k] = x
# Propagate the change upwards to parent nodes
while k > 1:
# Parent node (k >> 1) stores the maximum of its children (k and k ^ 1)
new_max = max(self.data[k], self.data[k ^ 1])
# Optimization: If parent value doesn't change, stop propagation.
if self.data[k >> 1] == new_max:
break
self.data[k >> 1] = new_max
k >>= 1
# Query maximum value in the range [l, r) (0-indexed, exclusive of r)
def query(self, l, r):
# Handle invalid or empty range queries
if l >= r:
return 0
# Map range [l, r) to segment tree array indices
L = l + self.actual_size; R = r + self.actual_size
s = 0 # Initialize maximum value found to 0
# Iteratively traverse up the tree from leaves L and R
while L < R:
# If R is the right child, include its sibling node's range and move R left
if R & 1:
R -= 1
s = max(s, self.data[R])
# If L is the left child, include its value and move L right to its sibling
if L & 1:
s = max(s, self.data[L])
L += 1
# Move up to the parent level
L >>= 1; R >>= 1
return s
# Store segment trees for each index k. segment_trees[k] will hold a tuple (ST_up_k, ST_down_k).
# ST_up_k stores max dp_up[j][k] (length ending j,k with A[j]<A[k]) indexed by rank(A[j]).
# ST_down_k stores max dp_down[j][k] (length ending j,k with A[j]>A[k]) indexed by rank(A[j]).
# Note: This list could potentially consume large memory if N and D are large.
segment_trees = [None] * N
# Variable to keep track of the maximum valid sequence length found so far (must be >= 3).
max_len = 0
# Iterate through each element A[k] which acts as the potential last element of a subsequence.
for k in range(N):
# Initialize segment trees for the current index k.
# These trees will store information about sequences ending at index k.
st_up_k = SegmentTree(D)
st_down_k = SegmentTree(D)
A_k = A[k] # Height of the current last element
rank_A_k = rank[A_k] # Rank of the height A[k]
# Iterate through each element A[j] (where j < k) which acts as the potential second to last element.
for j in range(k):
A_j = A[j] # Height of the second to last element
rank_A_j = rank[A_j] # Rank of the height A[j]
# Check if A_j and A_k are identical.
# A valid sequence requires distinct adjacent elements for the condition check (B_i != B_{i+1} implied).
# Also, the triplet condition (B_{i-1}, B_i, B_{i+1}) requires all three heights to be distinct.
# If A_j == A_k, this pair cannot be the last two elements of a valid sequence of length >= 3.
if A_j == A_k:
continue # Skip this pair (j, k)
# The base length for any pair (A_j, A_k) with A_j != A_k is 2.
# This represents a potential starting point for a longer sequence.
current_base_len = 2
# Initialize DP values for the current pair (j, k)
current_dp_up = 0 # Max length ending A_j, A_k where A_j < A_k (A_k is peak relative to A_j)
current_dp_down = 0 # Max length ending A_j, A_k where A_j > A_k (A_k is valley relative to A_j)
# Retrieve the segment trees associated with index j, which contain info about sequences ending at j.
prev_sts = segment_trees[j]
# Handle the base case where j=0. No previous element i exists. Can only form length 2 sequences.
if prev_sts is None:
if A_j < A_k:
current_dp_up = current_base_len
else: # A_j > A_k
current_dp_down = current_base_len
# If j > 0, we can potentially extend sequences ending at j.
else:
st_up_j, st_down_j = prev_sts # Unpack the trees for index j
# Case 1: A_j < A_k. This implies A_k is potentially a peak.
# The previous element A_j must have been a valley relative to (A_i, A_k).
# This requires extending a sequence ending in state `down` at index j.
if A_j < A_k:
# Query max dp_down[i][j] from ST_down[j]. Conditions: i < j, A_i > A_j, and A_i != A_k.
# The query needs to cover ranks corresponding to heights > A_j, excluding A_k.
# Query max length in height range (A_j, A_k) -> ranks (rank_A_j, rank_A_k)
max_val1 = st_down_j.query(rank_A_j + 1, rank_A_k)
# Query max length in height range (A_k, infinity) -> ranks (rank_A_k + 1, D)
max_val2 = st_down_j.query(rank_A_k + 1, D)
# Find the maximum length among valid precursors
best_prev_len = max(max_val1, max_val2)
# If a valid precursor sequence of length >= 2 is found, we can extend it.
if best_prev_len >= 2:
current_dp_up = max(current_base_len, best_prev_len + 1)
else: # Otherwise, the best we can do is start a new sequence of length 2.
current_dp_up = current_base_len
# Case 2: A_j > A_k. This implies A_k is potentially a valley.
# The previous element A_j must have been a peak relative to (A_i, A_k).
# This requires extending a sequence ending in state `up` at index j.
else: # A_j > A_k
# Query max dp_up[i][j] from ST_up[j]. Conditions: i < j, A_i < A_j, and A_i != A_k.
# The query needs to cover ranks corresponding to heights < A_j, excluding A_k.
# Query max length in height range (-infinity, A_k) -> ranks [0, rank_A_k)
max_val1 = st_up_j.query(0, rank_A_k)
# Query max length in height range (A_k, A_j) -> ranks (rank_A_k + 1, rank_A_j)
max_val2 = st_up_j.query(rank_A_k + 1, rank_A_j)
# Find the maximum length among valid precursors
best_prev_len = max(max_val1, max_val2)
# If a valid precursor sequence of length >= 2 is found, extend it.
if best_prev_len >= 2:
current_dp_down = max(current_base_len, best_prev_len + 1)
else: # Otherwise, start a new sequence of length 2.
current_dp_down = current_base_len
# Update segment trees for index k with the computed lengths.
# The update operation stores the max length sequence ending with (A_j, A_k)
# at the position corresponding to rank(A_j) in the trees for k.
if current_dp_up > 0:
st_up_k.update(rank_A_j, current_dp_up)
# If the new length is >= 3, update the overall maximum length found.
if current_dp_up >= 3: max_len = max(max_len, current_dp_up)
if current_dp_down > 0:
st_down_k.update(rank_A_j, current_dp_down)
# Update overall maximum length if >= 3.
if current_dp_down >= 3: max_len = max(max_len, current_dp_down)
# Store the pair of segment trees computed for index k. This information will be used
# for subsequent indices `k' > k` when `k` acts as the second-to-last element `j`.
segment_trees[k] = (st_up_k, st_down_k)
# Final Result: The problem asks for the maximum M.
# Valid M are 0 or M>=3 satisfying conditions.
# If max_len found is less than 3, the maximum valid length is 0.
if max_len < 3:
print(0)
else:
print(max_len)
# Execute the solve function
solve()