結果

問題 No.1332 Range Nearest Query
ユーザー wolgnikwolgnik
提出日時 2021-01-08 22:58:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,197 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,000 KB
実行使用メモリ 169,652 KB
最終ジャッジ日時 2024-04-28 04:42:15
合計ジャッジ時間 74,405 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
54,024 KB
testcase_01 AC 41 ms
53,076 KB
testcase_02 AC 43 ms
53,724 KB
testcase_03 TLE -
testcase_04 TLE -
testcase_05 TLE -
testcase_06 AC 860 ms
162,268 KB
testcase_07 AC 853 ms
161,636 KB
testcase_08 AC 855 ms
161,692 KB
testcase_09 AC 854 ms
162,076 KB
testcase_10 AC 836 ms
161,704 KB
testcase_11 AC 860 ms
162,336 KB
testcase_12 AC 839 ms
162,068 KB
testcase_13 AC 840 ms
162,292 KB
testcase_14 AC 815 ms
161,676 KB
testcase_15 AC 864 ms
161,892 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 504 ms
160,080 KB
testcase_27 AC 496 ms
159,660 KB
testcase_28 AC 406 ms
96,156 KB
testcase_29 AC 553 ms
98,200 KB
testcase_30 AC 646 ms
98,452 KB
testcase_31 AC 248 ms
91,488 KB
testcase_32 AC 642 ms
98,132 KB
testcase_33 AC 684 ms
98,392 KB
testcase_34 AC 331 ms
95,812 KB
testcase_35 AC 416 ms
96,276 KB
testcase_36 AC 417 ms
96,156 KB
testcase_37 AC 589 ms
97,432 KB
testcase_38 AC 1,862 ms
121,092 KB
testcase_39 AC 853 ms
98,228 KB
testcase_40 TLE -
testcase_41 AC 1,100 ms
103,880 KB
testcase_42 AC 1,689 ms
118,564 KB
testcase_43 AC 1,290 ms
109,584 KB
testcase_44 AC 2,296 ms
144,668 KB
testcase_45 AC 2,127 ms
138,940 KB
testcase_46 AC 1,624 ms
115,256 KB
testcase_47 AC 1,902 ms
126,476 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