Range Query

2 secs 1024 MB
shogo314's icon shogo314
Tweet
問題
提出
テストケース
解説

問題文

下のコードと同じ出力をするプログラムを書いてください。ただし、下のコードではTLEとなることに注意してください。

入力は、下のコードが正常終了するものである。

Python3
import bisect
T = int(input())
for _ in range(T):
    A, B, C = map(int, input().split())
    R = range(A, B, C)
    q = int(input())
    if q == 0:
        print(sum(R))
    elif q == 1:
        print(len(R))
    elif q == 2:
        x = int(input())
        assert 0 <= x < len(R)
        print(R[x])
    elif q == 3:
        x = int(input())
        assert x in R
        print(R.index(x))
    elif q == 4:
        x = int(input())
        print(R.count(x))
    elif q == 5:
        assert C > 0
        x = int(input())
        print(bisect.bisect_left(R, x))
    elif q == 6:
        assert C > 0
        x = int(input())
        print(bisect.bisect_right(R, x))
    else:
        exit(1)

Pythonのrangeの仕様に関する簡単な説明

range(start,stop,step) の形で引数を与える。このとき、step が 00 だと ValueError となる。
step >0> 0 のときは

Python3
v = []
i = start
while i < stop:
    v.append(i)
    i += step

というコードで得られる v のように扱える。step <0< 0 のときは

Python3
v = []
i = start
while i > stop:
    v.append(i)
    i += step

である。

制約

  • 1≤T≤2×1051 \leq T \leq 2 \times 10^5
  • −109≤A≤109-10^9 \leq A \leq 10^9
  • −109≤B≤109-10^9 \leq B \leq 10^9
  • −109≤C≤109-10^9 \leq C \leq 10^9
  • 0≤q≤60 \leq q \leq 6
  • −2×109≤x≤2×109-2 \times 10^9 \leq x \leq 2 \times 10^9

入力

入力は以下の形式で標準入力から与えられる。

QQ
query11
query22
⋮\vdots
queryQQ

ii 番目のクエリ queryii では、クエリの種類 qq と必要に応じて xx が下の形で与えられる。

qq

qq
xx

出力

答えは TT 行である。

入力例 1

3
100 150 3
0
10 -120 -1
3
3
8 2 3
4
8

出力例 1

2108
7
0

入力例 2

1
-100000000 100000000 1
1

出力例 2

200000000

提出

Go (1.21)