結果

問題 No.1332 Range Nearest Query
ユーザー wolgnikwolgnik
提出日時 2021-01-08 23:01:34
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,308 bytes
コンパイル時間 742 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 165,888 KB
最終ジャッジ日時 2024-11-16 15:13:49
合計ジャッジ時間 63,445 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 41 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

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