結果

問題 No.3565 Take from Excluded
コンテスト
ユーザー titia
提出日時 2026-06-05 22:40:48
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 1,552 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 216 ms
コンパイル使用メモリ 85,632 KB
実行使用メモリ 311,296 KB
最終ジャッジ日時 2026-06-05 22:41:10
合計ジャッジ時間 4,670 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

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
    

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

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

        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