結果

問題 No.3524 二進範囲更新範囲和取得
コンテスト
ユーザー 👑 amentorimaru
提出日時 2026-05-01 23:18:36
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 1,188 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 135 ms
コンパイル使用メモリ 85,376 KB
実行使用メモリ 133,196 KB
最終ジャッジ日時 2026-05-01 23:18:59
合計ジャッジ時間 6,930 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import math
input = sys.stdin.readline
def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
from fractions import Fraction

def main():  
  # オーバーフロー上等の問題で遅延セグもどきを作っては普通につらいなり……
  n,b,q=read_values()
  a=[[0]*b for v in range(n+1)]
  ab=[0]*(n+1)
  m=[1]*(n+1)
  for v in range(n,0,-1):
    a[v][v%b]+=1
    ab[v]=v%b
    if v>1:
      for i in range(b):
        a[v//2][i]+=a[v][i]
  for _ in range(q):
    ii,dd=read_values()
    m[ii]*=dd
    v=ii
    rev=-1
    mul=1
    while v:
      mul*=m[v]
      if rev!=-1:
        if rev==v*2:
          m[v*2+1]*=m[v]
        else:
          m[v*2]*=m[v]
      m[v]=1
      rev=v
      v//=2
    na=[0]*b
    for bb in range(b):
      na[(pow(bb,mul,b)+1)%b]+=a[v][bb]
    a[ii]=na
    v=ii//2
    while v:
      na=[0]*b
      for bb in range(b):
        na[bb]=a[v*2][bb]+a[v*2+1][bb]
      a[v]=na
      v//=2
    ans=0
    for bb in range(b):
      ans+=bb*a[1][bb]
    print(ans%b)
    


    
      
if __name__ == "__main__":
  main()
0