結果

問題 No.3446 Range Adjacent Differences
ユーザー kidodesu
提出日時 2026-02-11 22:38:12
言語 PyPy3
(7.3.17)
結果
TLE  
実行時間 -
コード長 3,499 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 211 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 225,728 KB
最終ジャッジ日時 2026-02-18 20:50:47
合計ジャッジ時間 5,298 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from math import isqrt
from collections import defaultdict
D = [0] * 2 * (10 ** 7 + 1)
X = [[0 for _ in range(1<<i*6)] for i in range(4)]
Y = [[0 for _ in range(1<<i*6)] for i in range(4)]

def add(Z, a):
    for i in range(3, -1, -1):
        a0 = a & 63
        a >>= 6
        Z[i][a] |= 1 << a0
    return

def dec(Z, a):
    for i in range(3, -1, -1):
        a0 = a & 63
        a >>= 6
        Z[i][a] ^= 1 << a0
        if Z[i][a]:
            break
    return

def bsl(Z, a):
    a += 1
    for i in range(3, -1, -1):
        if Z[i][a >> 6] & (1 << (a & 63)) - 1:
            rep = ((a >> 6) << 6) | (Z[i][a >> 6] & (1 << (a & 63)) - 1).bit_length()-1
            break
        a >>= 6
    else:
        return -1
    for j in range(i+1, 4):
        rep = (rep << 6) | Z[j][rep].bit_length()-1
    return rep

def bsr(Z, a):
    a -= 1
    for i in range(3, -1, -1):
        ma = 0
        if a & 63 != 63:
            ma = ~((1 << ((a&63)+1)) - 1)
        if Z[i][a >> 6] & ma:
            x = Z[i][a >> 6] & ma
            rep = ((a >> 6) << 6) | (x & -x).bit_length()-1
            break
        a >>= 6
    else:
        return -1
    for j in range(i+1, 4):
        rep = (rep << 6) | (Z[j][rep] & -Z[j][rep]).bit_length()-1
    return rep


n, q = list(map(int, input().split()))
Ans = [-1] * q
A = list(map(int, input().split()))

Q_size = isqrt(n)
Q_cnt = (n + Q_size - 1) // Q_size
Q = [[] for _ in range(Q_cnt)]

for _ in range(q):
    *P, c = list(map(str, input().split()))
    l, r, x = list(map(int, P))
    l -= 1
    if c == "L":
        t = 0
    else:
        t = 1
    Q[l // Q_size].append((t, l, r, x, _))
    

for qi in range(Q_cnt):
    if not qi % 2:
        Q[qi].sort(key = lambda x: x[2])
    else:
        Q[qi].sort(key = lambda x: -x[2])

def f0(a):
    D[a] += 1
    if 1 < D[a]:
        global cnt0
        cnt0 += 1
        return
    al = bsl(X, a)
    ar = bsr(X, a)
    add(X, a)
    if al == -1 and ar == -1:
        pass
    elif ar == -1:
        D[al-a] += 1
        if D[al-a] == 1:
            add(Y, a-al)
    elif al == -1:
        D[a-ar] += 1
        if D[a-ar] == 1:
            add(Y, ar-a)
    else:
        D[al-ar] -= 1
        if D[al-ar] == 0:
            dec(Y, ar-al)
        D[a-ar] += 1
        if D[a-ar] == 1:
            add(Y, ar-a)
        D[al-a] += 1
        if D[al-a] == 1:
            add(Y, a-al)

def f1(a):
    D[a] -= 1
    if D[a]:
        global cnt0
        cnt0 -= 1
        return
    dec(X, a)
    al = bsl(X, a)
    ar = bsr(X, a)
    if al == -1 and ar == -1:
        pass
    elif ar == -1:
        D[al-a] -= 1
        if D[al-a] == 0:
            dec(Y, a-al)
    elif al == -1:
        D[a-ar] -= 1
        if D[a-ar] == 0:
            dec(Y, ar-a)
    else:
        D[al-ar] += 1
        if D[al-ar] == 1:
            add(Y, ar-al)
        D[a-ar] -= 1
        if D[a-ar] == 0:
            dec(Y, ar-a)
        D[al-a] -= 1
        if D[al-a] == 0:
            dec(Y, a-al)

nl = nr = 0
cnt0 = 0
for qi in range(Q_cnt):
    for t, l, r, x, idx in Q[qi]:
        while l < nl:
            nl -= 1
            f0(A[nl])
        while nr < r:
            f0(A[nr])
            nr += 1
        while nl < l:
            f1(A[nl])
            nl += 1
        while r < nr:
            nr -= 1
            f1(A[nr])
        if not t:
            Ans[idx] = bsl(Y, x)
            if cnt0:
                Ans[idx] = max(Ans[idx], 0)
        else:
            Ans[idx] = bsr(Y, x)

for ans in Ans:
    print(ans)
0