結果

問題 No.2933 Range ROT Query
コンテスト
ユーザー 👑 loop0919
提出日時 2026-09-07 23:04:55
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,043 ms / 3,000 ms
+ 345µs
コード長 1,811 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,037 ms
コンパイル使用メモリ 81,024 KB
実行使用メモリ 107,136 KB
最終ジャッジ日時 2026-09-07 23:05:53
合計ジャッジ時間 48,335 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from atcoder.fenwicktree import FenwickTree
from atcoder.lazysegtree import LazySegTree

sigma = 26


emptyset = -1
wildcard = 9999


def op(x, y):
    if x == emptyset or y == emptyset:
        return emptyset

    if x == wildcard:
        return y

    if y == wildcard:
        return x

    if x == y:
        return x
    else:
        return emptyset


e = wildcard


def mapping(f, x):
    if x == emptyset or x == wildcard:
        return x

    return (x + f) % sigma


def composition(f, g):
    return (f + g) % sigma


id_ = 0


S = input()
T = input()

diff = []

for s, t in zip(S, T):
    diff.append((ord(s) - ord(t)) % sigma)

seg = LazySegTree(op, e, mapping, composition, id_, diff)

s_imos = FenwickTree(len(S) + 1)
t_imos = FenwickTree(len(T) + 1)

Q = int(input())

for _ in range(Q):
    cmd, *query = [int(s) for s in input().split()]

    if cmd == 1:
        l, r, x = query

        seg.apply(min(l - 1, len(S), len(T)), min(r, len(S), len(T)), x)
        s_imos.add(l - 1, x)
        s_imos.add(r, -x)

    elif cmd == 2:
        l, r, x = query

        seg.apply(min(l - 1, len(S), len(T)), min(r, len(S), len(T)), -x % sigma)
        t_imos.add(l - 1, x)
        t_imos.add(r, -x)

    else:
        p = query[0]

        idx = seg.max_right(p - 1, lambda x: x == 0 or x == wildcard)

        if idx < min(len(S), len(T)):
            s = (s_imos.sum(0, idx + 1) + ord(S[idx]) - ord("a")) % sigma
            t = (t_imos.sum(0, idx + 1) + ord(T[idx]) - ord("a")) % sigma

            if s > t:
                print("Greater")
            elif s < t:
                print("Lesser")

        else:
            if len(S) > len(T):
                print("Greater")
            elif len(S) < len(T):
                print("Lesser")
            else:
                print("Equals")
0