結果

問題 No.1332 Range Nearest Query
ユーザー wolgnikwolgnik
提出日時 2021-01-08 22:58:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,197 bytes
コンパイル時間 442 ms
コンパイル使用メモリ 82,328 KB
実行使用メモリ 170,132 KB
最終ジャッジ日時 2024-11-16 15:03:51
合計ジャッジ時間 67,485 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
52,224 KB
testcase_01 AC 42 ms
52,736 KB
testcase_02 AC 41 ms
52,864 KB
testcase_03 AC 2,381 ms
151,660 KB
testcase_04 AC 2,362 ms
148,976 KB
testcase_05 AC 2,384 ms
151,928 KB
testcase_06 AC 792 ms
161,824 KB
testcase_07 AC 801 ms
161,576 KB
testcase_08 AC 792 ms
161,572 KB
testcase_09 AC 800 ms
161,308 KB
testcase_10 AC 782 ms
161,444 KB
testcase_11 AC 804 ms
161,696 KB
testcase_12 AC 822 ms
161,708 KB
testcase_13 AC 809 ms
161,836 KB
testcase_14 AC 794 ms
161,636 KB
testcase_15 AC 803 ms
161,576 KB
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 AC 479 ms
159,696 KB
testcase_27 AC 497 ms
159,712 KB
testcase_28 AC 404 ms
95,892 KB
testcase_29 AC 537 ms
97,568 KB
testcase_30 AC 609 ms
98,452 KB
testcase_31 AC 240 ms
91,616 KB
testcase_32 AC 598 ms
98,132 KB
testcase_33 AC 608 ms
98,232 KB
testcase_34 AC 309 ms
95,388 KB
testcase_35 AC 391 ms
96,288 KB
testcase_36 AC 380 ms
96,024 KB
testcase_37 AC 539 ms
97,696 KB
testcase_38 AC 1,578 ms
121,148 KB
testcase_39 AC 735 ms
98,356 KB
testcase_40 AC 2,449 ms
163,356 KB
testcase_41 AC 992 ms
103,948 KB
testcase_42 AC 1,578 ms
118,552 KB
testcase_43 AC 1,262 ms
108,756 KB
testcase_44 AC 2,067 ms
144,360 KB
testcase_45 AC 1,900 ms
139,264 KB
testcase_46 AC 1,470 ms
115,060 KB
testcase_47 AC 1,733 ms
125,904 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

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 l, r, x, i in qs:
  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 l, r, x, i in qs:
  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