結果

問題 No.1332 Range Nearest Query
ユーザー wolgnikwolgnik
提出日時 2021-01-08 23:01:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,467 ms / 2,500 ms
コード長 3,308 bytes
コンパイル時間 206 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 165,244 KB
最終ジャッジ日時 2024-04-28 04:49:04
合計ジャッジ時間 58,656 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
52,480 KB
testcase_01 AC 40 ms
52,480 KB
testcase_02 AC 40 ms
52,480 KB
testcase_03 AC 2,102 ms
142,912 KB
testcase_04 AC 2,044 ms
142,796 KB
testcase_05 AC 2,081 ms
140,356 KB
testcase_06 AC 646 ms
151,988 KB
testcase_07 AC 642 ms
152,124 KB
testcase_08 AC 644 ms
151,864 KB
testcase_09 AC 641 ms
155,960 KB
testcase_10 AC 648 ms
154,808 KB
testcase_11 AC 645 ms
151,988 KB
testcase_12 AC 646 ms
152,116 KB
testcase_13 AC 651 ms
152,496 KB
testcase_14 AC 639 ms
151,992 KB
testcase_15 AC 651 ms
152,500 KB
testcase_16 AC 2,337 ms
165,124 KB
testcase_17 AC 2,317 ms
164,608 KB
testcase_18 AC 2,404 ms
165,132 KB
testcase_19 AC 2,399 ms
164,752 KB
testcase_20 AC 2,349 ms
165,244 KB
testcase_21 AC 2,330 ms
164,100 KB
testcase_22 AC 2,467 ms
164,612 KB
testcase_23 AC 2,423 ms
164,740 KB
testcase_24 AC 2,339 ms
164,228 KB
testcase_25 AC 2,322 ms
164,620 KB
testcase_26 AC 425 ms
155,724 KB
testcase_27 AC 459 ms
161,028 KB
testcase_28 AC 284 ms
83,940 KB
testcase_29 AC 422 ms
85,928 KB
testcase_30 AC 484 ms
85,616 KB
testcase_31 AC 177 ms
83,728 KB
testcase_32 AC 483 ms
87,036 KB
testcase_33 AC 501 ms
87,356 KB
testcase_34 AC 222 ms
83,736 KB
testcase_35 AC 296 ms
84,376 KB
testcase_36 AC 293 ms
84,152 KB
testcase_37 AC 430 ms
85,908 KB
testcase_38 AC 1,414 ms
111,112 KB
testcase_39 AC 643 ms
94,168 KB
testcase_40 AC 2,232 ms
155,532 KB
testcase_41 AC 838 ms
95,792 KB
testcase_42 AC 1,332 ms
110,112 KB
testcase_43 AC 1,046 ms
99,116 KB
testcase_44 AC 1,815 ms
135,364 KB
testcase_45 AC 1,671 ms
126,972 KB
testcase_46 AC 1,259 ms
105,124 KB
testcase_47 AC 1,486 ms
113,764 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
Q = int(input())
ls = [0] * Q
rs = [0] * Q
xs = [0] * Q
qs = []

for i in range(Q):
  l, r, x = map(int, input().split())
  l -= 1
  ls[i] = l
  rs[i] = r
  xs[i] = x
  qs.append(i)
qs.sort(key = lambda x: xs[x])

class maxSegTree:
  def segfunc(self, x, y):
    return max(x, y)
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res

s = []
for i in range(N): s.append((a[i], i))
s.sort(reverse = True)

seg = maxSegTree(N, 0, [0] * N)
inf = 10 ** 10
res = [inf] * Q
for i in qs:
  l, r, x = ls[i], rs[i], xs[i]
  while len(s) and s[-1][0] <= x:
    y, j = s.pop()
    seg.update(j, y)
  q = seg.query(l, r)
  if q: res[i] = x - q
#print(res)


class minSegTree:
  def segfunc(self, x, y):
    return min(x, y)
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res

s = []
for i in range(N): s.append((a[i], i))
s.sort()
qs.reverse()

seg = minSegTree(N, inf, [inf] * N)
inf = 10 ** 10
for i in qs:
  l, r, x = ls[i], rs[i], xs[i]
  while len(s) and s[-1][0] >= x:
    y, j = s.pop()
    seg.update(j, y)
  q = seg.query(l, r)
  if q: res[i] = min(res[i], q - x)

for r in res: print(r)
0