結果

問題 No.3565 Take from Excluded
コンテスト
ユーザー titia
提出日時 2026-06-05 23:00:53
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,366 ms / 2,000 ms
コード長 1,898 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 171 ms
コンパイル使用メモリ 85,504 KB
実行使用メモリ 308,092 KB
最終ジャッジ日時 2026-06-05 23:01:19
合計ジャッジ時間 8,534 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

def nec(X,k):
    ko=k
    Y=[]
    for i in range(len(X)):
        a,b=X[i]

        if i+1<len(X):
            c,d=X[i+1]
        else:
            c,d=1<<63,1<<63

        minus=c-(a+b)

        MIN=min(ko,minus)
        ko-=MIN

        Y.append([a+b,MIN])

        if ko==0:
            break
    return Y

def what(X,x):
    for i in range(len(X)):
        a,b=X[i]
        if b>=x:
            return a+(x-1)
        else:
            x-=b
    

def kai(X,k,m):
    if k%2==1:
        X=nec(X,m)
        k-=1

    Y=nec(X,m)

    necfirst=Y[-1][0]+Y[-1][1]
    first=X[0][0]

    Y=[]
    for a,b in X:
        Y.append([a+(necfirst-first),b])

    X=X+Y

    return X[k//2:k//2+len(X)//2]

    

mod=998244353

N,Q=list(map(int,input().split()))
A=list(map(int,input().split()))
A=sorted(set(A))

X=[]
for a in A:
    if X==[] or X[-1][0]+X[-1][1]!=a:
        X.append([a,1])
    else:
        X[-1][1]+=1

#print(X)

plus=0
for tests in range(Q):
    k,x,m=list(map(int,input().split()))

    if k<=5:

        for tt in range(k):
            X=nec(X,m)

        print((what(X,x)+plus)%mod)
    else:
        #print("!",X)
        Y=nec(X,m)
        Z=nec(Y,m)
        k-=1

        while len(Y)!=len(Z):
            Y=Z
            Z=nec(Y,m)
            k-=1
            

        #print(Y)
        #print(Z)

        LEN=len(Y)+len(Z)

        a,b=Z[-1]
        necfirst=a+b
        first=Y[0][0]

        shuuki=necfirst-first


        rep=k//(LEN)
        k%=(LEN)
        plus=(plus+shuuki*rep)%mod

        Y=kai(Y,k,m)

        #print("!",Y1)

        #for tt in range(k):
        #    Y=nec(Y,m)

        #print("?",Y)

        #assert Y==Y1


        X=Y
        if X[0][0]>=mod:
            k=X[0][0]//mod

            for i in range(len(X)):
                X[i][0]-=k*mod
        print((what(X,x)+plus)%mod)
0