結果
| 問題 | No.1332 Range Nearest Query |
| コンテスト | |
| ユーザー |
 kemuniku
|
| 提出日時 | 2026-04-21 04:13:37 |
| 言語 | Nim (2.2.8) |
| 結果 |
AC
|
| 実行時間 | 1,025 ms / 2,500 ms |
| コード長 | 11,396 bytes |
| 記録 | |
| コンパイル時間 | 7,202 ms |
| コンパイル使用メモリ | 78,080 KB |
| 実行使用メモリ | 15,744 KB |
| 最終ジャッジ日時 | 2026-04-21 04:14:32 |
| 合計ジャッジ時間 | 38,422 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 48 |
ソースコード
import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
# source: src/cplib/tmpl/sheep.nim
ImportExpand "cplib/tmpl/sheep" <=== "when not declared CPLIB_TMPL_SHEEP:\n const CPLIB_TMPL_SHEEP* = 1\n {.warning[UnusedImport]: off.}\n {.hint[XDeclaredButNotUsed]: off.}\n import algorithm\n import sequtils\n import tables\n import macros\n import math\n import sets\n import strutils\n import strformat\n import sugar\n import heapqueue\n import streams\n import deques\n import bitops\n import std/lenientops\n import options\n #入力系\n proc scanf(formatstr: cstring){.header: \"<stdio.h>\", varargs.}\n proc getchar(): char {.importc: \"getchar_unlocked\", header: \"<stdio.h>\", discardable.}\n proc ii(): int {.inline.} = scanf(\"%lld\\n\", addr result)\n proc lii(N: int): seq[int] {.inline.} = newSeqWith(N, ii())\n proc si(): string {.inline.} =\n result = \"\"\n var c: char\n while true:\n c = getchar()\n if c == ' ' or c == '\\n' or c == '\\255':\n break\n result &= c\n \n # 出力系\n # 1. 実際の処理を行う proc (openArray を受け取る)\n proc print_internal(prop: tuple[f: File, sepc: string, endc: string, flush: bool], args: openArray[string]) =\n for i in 0 ..< args.len:\n prop.f.write(args[i])\n if i != args.len - 1:\n prop.f.write(prop.sepc)\n else:\n prop.f.write(prop.endc)\n if prop.flush:\n prop.f.flushFile()\n\n # 2. ユーザーが呼び出すためのインターフェース (varargs を受け取る)\n proc print*(prop: tuple[f: File, sepc: string, endc: string, flush: bool], args: varargs[string, `$`]) =\n # varargs は内部では openArray として扱えるので、そのまま渡せる\n print_internal(prop, args)\n\n proc print*(args: varargs[string, `$`]) =\n # こちらも内部用の proc を呼ぶ\n print_internal((f: stdout, sepc: \" \", endc: \"\\n\", flush: false), args)\n macro getSymbolName(x: typed): string = x.toStrLit\n macro debug*(args: varargs[untyped]): untyped =\n when defined(debug):\n result = newNimNode(nnkStmtList, args)\n template prop(e: string = \"\"): untyped = (f: stderr, sepc: \"\", endc: e, flush: true)\n for i, arg in args:\n if arg.kind == nnkStrLit:\n result.add(quote do: print(prop(), \"\\\"\", `arg`, \"\\\"\"))\n else:\n result.add(quote do: print(prop(\": \"), getSymbolName(`arg`)))\n result.add(quote do: print(prop(), `arg`))\n if i != args.len - 1: result.add(quote do: print(prop(), \", \"))\n else: result.add(quote do: print(prop(), \"\\n\"))\n else:\n return (quote do: discard)\n #chmin,chmax\n template `max=`(x, y) =\n let yVal = y # yが計算式の場合に評価を1回にするため\n if x < yVal:\n x = yVal\n\n template `min=`(x, y) =\n let yVal = y\n if x > yVal:\n x = yVal\n proc chmin[T](x: var T, y: T):bool=\n if x > y:\n x = y\n return true\n return false\n proc chmax[T](x: var T, y: T):bool=\n if x < y:\n x = y\n return true\n return false\n #bit演算\n proc `%`*(x: int, y: int): int =\n result = x mod y\n if y > 0 and result < 0: result += y\n if y < 0 and result > 0: result += y\n proc `//`*(x: int, y: int): int{.inline.} =\n result = x div y\n if y > 0 and result * y > x: result -= 1\n if y < 0 and result * y < x: result -= 1\n proc `%=`(x: var int, y: int): void = x = x%y\n proc `//=`(x: var int, y: int): void = x = x//y\n proc `**`(x: int, y: int): int = x^y\n proc `**=`(x: var int, y: int): void = x = x^y\n proc `^`(x: int, y: int): int = x xor y\n proc `|`(x: int, y: int): int = x or y\n proc `&`(x: int, y: int): int = x and y\n proc `>>`(x: int, y: int): int = x shr y\n proc `<<`(x: int, y: int): int = x shl y\n proc `~`(x: int): int = not x\n proc `^=`(x: var int, y: int): void = x = x ^ y\n proc `&=`(x: var int, y: int): void = x = x & y\n proc `|=`(x: var int, y: int): void = x = x | y\n proc `>>=`(x: var int, y: int): void = x = x >> y\n proc `<<=`(x: var int, y: int): void = x = x << y\n proc `[]`(x: int, n: int): bool = (x and (1 shl n)) != 0\n #便利な変換\n proc `!`(x: char, a = '0'): int = int(x)-int(a)\n #定数\n when not declared CPLIB_UTILS_CONSTANTS:\n const CPLIB_UTILS_CONSTANTS* = 1\n const INF32*: int32 = 1001000027.int32\n const INF64*: int = int(3300300300300300491)\n \n const INF = INF64\n #converter\n\n #range\n iterator range(start: int, ends: int, step: int): int =\n var i = start\n if step < 0:\n while i > ends:\n yield i\n i += step\n elif step > 0:\n while i < ends:\n yield i\n i += step\n iterator range(ends: int): int = (for i in 0..<ends: yield i)\n iterator range(start: int, ends: int): int = (for i in\n start..<ends: yield i)\n\n #joinが非stringでめちゃくちゃ遅いやつのパッチ\n proc join*[T: not string](a: openArray[T], sep: string = \"\"): string = a.mapit($it).join(sep)\n\n proc dump[T](arr:seq[seq[T]])=\n for i in 0..<len(arr):\n echo arr[i]\n\n proc sum(slice:HSlice[int,int]):int=\n return (slice.a+slice.b)*len(slice)//2\n \n proc `<`[T](l,r:seq[T]):bool=\n for i in 0..<min(len(l),len(r)):\n if l[i] > r[i]:\n return false\n elif l[i] < r[i]:\n return true\n return len(l) < len(r)\n \n # Yes/No\n proc yes*(b: bool = true): void = print(if b: \"Yes\" else: \"No\")\n proc oo*(b: bool = true): void = yes(not b)\n\n proc takahashi(b:bool = true) : void = print(if b: \"Takahashi\" else: \"Aoki\")\n proc aoki(b:bool = true) : void = takahashi(not b)\n\n template dblock(body: untyped) =\n when defined(debug):\n block:\n body\n"
# source: src/cplib/collections/waveletmatrix.nim
ImportExpand "cplib/collections/waveletmatrix" <=== "when not declared CPLIB_COLLECTIONS_WAVELETMATRIX:\n const CPLIB_COLLECTIONS_WAVELETMATRIX* = 1\n when not declared CPLIB_COLLECTIONS_BITVECTOR:\n const CPLIB_COLLECTIONS_BITVECTOR* = 1\n import bitops\n import sequtils\n \n type BitVector* = object\n bits : seq[uint64]\n csum : seq[int]\n \n proc newBitVector*(length:int):BitVector=\n result.bits = newSeq[uint64]((length+63) div 64 + 1)\n result.csum = newSeq[int](((length+63) div 64)+1)\n \n proc set*(self:var BitVector,idx:int)=\n self.bits[idx div 64].setBit(idx mod 64)\n \n proc build*(self:var BitVector)=\n for i in 0..<(len(self.bits)-1):\n self.csum[i+1] = self.csum[i] + popcount(self.bits[i])\n \n proc access*(self:var BitVector,idx:int):bool=\n self.bits[idx div 64].testBit(idx mod 64)\n \n proc `[]`*(self:var BitVector,idx:int):bool=\n self.bits[idx div 64].testBit(idx mod 64)\n \n proc rank*(self:var BitVector,idx:int):int=\n return self.csum[idx div 64] + popcount(self.bits[idx div 64] and ((1u shl (idx and 63)) - 1))\n \n \n import sequtils\n import bitops\n\n type WaveletMatrix* = ref object\n dat : seq[BitVector]\n H : int\n N : int\n \n proc initWaveletMatrix*(v:seq[int],H:int):WaveletMatrix=\n var v = v\n var N = len(v)\n result = WaveletMatrix(dat:newSeqWith(H,newBitVector(N)),N:N,H:H)\n var zero,one = newseqwith(N,-1)\n var a = 0\n var b = 0\n for h in countdown(H-1,0,1):\n for i in 0..<N:\n if v[i].testBit(h):\n one[b] = v[i]\n b += 1\n result.dat[h].set(i)\n else:\n zero[a] = v[i]\n a += 1\n for i in 0..<a:\n v[i] = zero[i]\n for i in 0..<b:\n v[a+i] = one[i]\n a = 0\n b = 0\n result.dat[h].build()\n \n proc initWaveletMatrix*(v:seq[int]):WaveletMatrix=\n var x = v.max()\n if x == 0:\n return initWaveletMatrix(v,1)\n return initWaveletMatrix(v,x.fastLog2()+1)\n \n proc get_child*(self:WaveletMatrix,h,l,r:int):tuple[l0,r0,l1,r1:int]=\n # 高さh+1における[l,r)に該当する部分を見ているとする。\n # その子に該当する部分を[l0,r0),[l1,r1)としたとき、(l0,r0,l1,r1)を返す。\n var c0 = self.N - self.dat[h].rank(self.N)\n result.l0 = l - self.dat[h].rank(l)\n result.r0 = r - self.dat[h].rank(r)\n result.l1 = self.dat[h].rank(l) + c0\n result.r1 = self.dat[h].rank(r) + c0\n\n \n proc kth_smallest*(self:WaveletMatrix,l,r,k:int):int=\n # [l,r) 内で、k番目に小さいものを出力\n var k = k\n var l = l\n var r = r\n for h in countdown(self.H-1,0,1):\n var (l0,r0,l1,r1) = self.get_child(h,l,r)\n if k < r0-l0:\n l = l0\n r = r0\n else:\n l = l1\n r = r1\n k -= r0-l0\n result += 1 shl h\n \n proc range_lowerbound*(self:WaveletMatrix,l,r,x:int):int=\n var x = x\n var l = l\n var r = r\n var now = 0\n for h in countdown(self.H-1,0,1):\n var (l0,r0,l1,r1) = self.get_child(h,l,r)\n if (now + 1 shl h) > x:\n l = l0\n r = r0\n else:\n l = l1\n r = r1\n now += 1 shl h\n result += r0-l0\n \n proc range_upperbound*(self:WaveletMatrix,l,r,x:int):int=\n var x = x\n var l = l\n var r = r\n var now = 0\n for h in countdown(self.H-1,0,1):\n var (l0,r0,l1,r1) = self.get_child(h,l,r)\n if (now + 1 shl h) >= x:\n l = l0\n r = r0\n else:\n l = l1\n r = r1\n now += 1 shl h\n result += r0-l0\n result += r-l"
#[
数直線上のN個の座標 X_1 , X_2 , ... , X_Nが与えられる。
以下のクエリがQ個与えられるので、順に処理してください。
l,rと座標xが与えられる。min(abs(X_i - x) i in l..r )を求めよ。
]#
var N = ii()
var X = lii(N)
var Q = ii()
var WM = X.initWaveletMatrix()
for _ in range(Q):
var l,r = ii()
l -= 1
var x = ii()
var res = INF
var a = WM.range_upperbound(l,r,x)-1
if a != -1:
res.min = x-WM.kth_smallest(l,r,a)
var b = WM.range_lowerbound(l,r,x)
if b != r-l:
res.min = WM.kth_smallest(l,r,b)-x
echo res