結果

問題 No.3788 Floor Sum Queries
コンテスト
ユーザー まぬお
提出日時 2026-11-06 23:08:45
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
RE  
実行時間 -
コード長 1,293 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 80 ms
コンパイル使用メモリ 64,256 KB
実行使用メモリ 60,780 KB
平均クエリ数 2.00
最終ジャッジ日時 2026-11-06 23:09:12
合計ジャッジ時間 3,314 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge7_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right, insort
from itertools import permutations, combinations, groupby
from heapq import heappop, heappush
import math, sys
def printl(li, sep=" "): print(sep.join(map(str, li)))
def yn(flag): print(Yes if flag else No)
_int = lambda x: int(x)-1
MOD = 998244353 #10**9+7
INF = 1<<60
Yes, No = "Yes", "No"

# https://github.com/manuo-git/python-lib/blob/main/src/floor_sum.py
# https://atcoder.jp/contests/abc443/editorial/15138
def floor_sum(n, m, a, b):
    a1, a2 = a//m, a%m
    s = n*(n-1)//2*a1
    b1, b2 = b//m, b%m
    if a2 == 0: return s+b1*n
    k = (a2*(n-1)+b2)//m
    return s+n*(k+b1)-floor_sum(k, a2, m, m+a2-b2-1)

K = 1000000
A = [K]
while K > 1:
    K = -(-K//2)
    A.append(K)
A.reverse()
# print(A)
# print(len(A))
K = len(A)

for _ in range(int(input())):
    D = dict()
    q = 0
    def value(m):
        b = A[m]
        if b in D: return D[b]
        global q
        q += 1
        print(f"? 0 {b}")
        res = int(input())
        D[b] = res
        return res

    def check(m):
        res = value(m)
        return res > 0

    l, r = -1, K
    while r-l>1:
        m = (l+r)//2
        if check(m): r = m
        else: l = m
    ans = value(r)
    print(f"! {ans}")
0