結果
| 問題 | No.3618 Omega Cat（Making ver.） |
| コンテスト | |
| ユーザー |
 kidodesu
|
| 提出日時 | 2026-08-06 16:07:54 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
AC
|
| 実行時間 | 1,137 ms / 2,000 ms |
| + 479µs | |
| コード長 | 4,171 bytes |
| 記録 | |
| コンパイル時間 | 223 ms |
| コンパイル使用メモリ | 95,852 KB |
| 実行使用メモリ | 146,148 KB |
| 最終ジャッジ日時 | 2026-08-06 16:10:45 |
| 合計ジャッジ時間 | 20,352 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge1_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| サンプル | 0 % | AC * 1 |
| 小課題1 | 20 % | AC * 5 |
| 小課題2 | 20 % | AC * 12 |
| 小課題3 | 40 % | AC * 24 |
| 小課題4 | 20 % | AC * 38 |
| 合計 | 3.5 * 100% = 350 点 |
ソースコード
class segtree:
n = 1
size = 1
log = 2
d = [0]
op = None
e = 10**15
def __init__(self, V, OP, E):
self.n = len(V)
self.op = OP
self.e = E
self.log = (self.n - 1).bit_length()
self.size = 1 << self.log
self.d = [E for i in range(2 * self.size)]
d = self.d
for i in range(self.n):
d[self.size + i] = V[i]
op = self.op
for i in range(self.size - 1, 0, -1):
d[i] = op(d[2 * i], d[2 * i + 1])
def set(self, p, x):
assert 0 <= p and p < self.n
d = self.d
op = self.op
p += self.size
d[p] = x
for i in range(1, self.log + 1):
k = p >> i
d[k] = op(d[2 * k], d[2 * k + 1])
def get(self, p):
assert 0 <= p and p < self.n
return self.d[p + self.size]
def prod(self, l, r):
assert 0 <= l and l <= r and r <= self.n
d = self.d
op = self.op
sml = self.e
smr = self.e
l += self.size
r += self.size
while l < r:
if l & 1:
sml = op(sml, d[l])
l += 1
if r & 1:
smr = op(d[r - 1], smr)
r -= 1
l >>= 1
r >>= 1
return op(sml, smr)
def all_prod(self):
return self.d[1]
def max_right(self, l, f):
assert 0 <= l and l <= self.n
assert f(self.e)
if l == self.n:
return self.n
d = self.d
op = self.op
size = self.size
l += size
sm = self.e
while 1:
while l % 2 == 0:
l >>= 1
if not (f(op(sm, d[l]))):
while l < size:
l = 2 * l
if f(op(sm, d[l])):
sm = op(sm, d[l])
l += 1
return l - size
sm = op(sm, d[l])
l += 1
if (l & -l) == l:
break
return self.n
def min_left(self, r, f):
assert 0 <= r and r <= self.n
assert f(self.e)
if r == 0:
return 0
d = self.d
op = self.op
size = self.size
r += size
sm = self.e
while 1:
r -= 1
while r > 1 and (r % 2):
r >>= 1
if not (f(op(d[r], sm))):
while r < size:
r = 2 * r + 1
if f(op(d[r], sm)):
sm = op(d[r], sm)
r -= 1
return r + 1 - size
sm = op(d[r], sm)
if (r & -r) == r:
break
return 0
def update(self, k):
self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
def __str__(self):
return str([self.get(i) for i in range(self.n)])
inf = 1<<30
def main():
n = int(input())
A = list(map(int, input().split()))
def cal(A):
n = len(A)
def op0(a, b): return max(a, b)
def op1(a, b): return min(a, b)
st0 = segtree([-inf]*(n+1), op0, -inf)
st1 = segtree([inf]*(n+1), op1, inf)
st0.set(0, inf)
st0.set(1, A[0])
if A[0] > A[1]:
st0.set(2, A[1])
st1.set(2, A[1])
st1.set(1, -inf)
else:
st0.set(1, A[1])
st1.set(1, -inf)
rep = [[-inf, -inf] for _ in range(n)]
for i in range(2, n):
a = A[i]
r = st1.min_left(n, lambda x: x == inf)
rep[i][0] = r-1
r = st1.min_left(n, lambda x: x >= a)
rep[i][1] = r-1
st1.set(r, a)
r = st0.min_left(n, lambda x: x == -inf)-1
st1.set(r-1, -inf)
r = st0.min_left(n, lambda x: x <= a)
st1.set(r, min(st1.get(r), a))
st0.set(r, a)
return rep
rep0 = cal(A)
rep1 = cal(A[::-1])[::-1]
ans = 0
for i in range(n):
ans = max(ans, rep0[i][0]+rep1[i][0], rep0[i][1]+rep1[i][1]+1)
return n-ans
for _ in range(int(input())):
print(main())