結果
| 問題 | No.3446 Range Adjacent Differences |
| ユーザー |
 kemuniku
|
| 提出日時 | 2026-02-19 04:14:22 |
| 言語 | Nim (2.2.6) |
| 結果 |
AC
|
| 実行時間 | 1,203 ms / 2,200 ms |
| コード長 | 11,581 bytes |
| 記録 | |
| コンパイル時間 | 6,551 ms |
| コンパイル使用メモリ | 81,384 KB |
| 実行使用メモリ | 103,408 KB |
| 最終ジャッジ日時 | 2026-02-19 04:14:47 |
| 合計ジャッジ時間 | 23,636 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
ソースコード
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 #chmin,chmax\n template `max=`(x, y) = x = max(x, y)\n template `min=`(x, y) = x = min(x, y)\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)"
# source: src/cplib/collections/wordsizetree.nim
ImportExpand "cplib/collections/wordsizetree" <=== "when not declared CPLIB_COLLECTIONS_WORD_SIZE_TREE:\n const CPLIB_COLLECTIONS_WORD_SIZE_TREE* = 1\n import bitops\n type WordsizeTree = object\n A0 : uint\n A1 : array[64,uint]\n A2 : array[64*64,uint]\n A3 : array[64*64*64,uint]\n\n proc initWordsizeTree*():WordsizeTree=\n discard\n\n proc initWordsizeTree*(v:seq[bool]):WordsizeTree=\n for i in 0..<len(v):\n if v[i]: result.A3[i shr 6] = result.A3[i shr 6] or (1u shl (i and(0b111111)))\n for i in 0..<((len(v)+(63)) shr 6):\n if result.A3[i] != 0:result.A2[i shr 6] = result.A2[i shr 6] or (1u shl (i and(0b111111)))\n for i in 0..<((len(v)+(64*64-1)) shr 12):\n if result.A2[i] != 0:result.A1[i shr 6] = result.A1[i shr 6] or (1u shl (i and(0b111111)))\n for i in 0..<((len(v)+(64*64*64-1)) shr 18):\n if result.A1[i] != 0:result.A0 = result.A0 or (1u shl (i and(0b111111)))\n\n\n proc incl*(self:var WordsizeTree,x:int)=\n var y = x and (0b111111)\n var x = x shr 6\n self.A3[x] = self.A3[x] or (1u shl y)\n y = x and (0b111111)\n x = x shr 6\n self.A2[x] = self.A2[x] or (1u shl y)\n y = x and (0b111111)\n x = x shr 6\n self.A1[x] = self.A1[x] or (1u shl y)\n y = x and (0b111111)\n x = x shr 6\n self.A0 = self.A0 or (1u shl y)\n\n proc `[]`*(self:var WordsizeTree,x:int):bool=\n var y = x and (0b111111)\n var x = x shr 6\n return (self.A3[x] and (1u shl y)) != 0\n\n proc excl*(self:var WordsizeTree,x:int)=\n if self[x]:\n var y = x and (0b111111)\n var x = x shr 6\n self.A3[x].clearBit(y)\n if self.A3[x] != 0:return\n y = x and (0b111111)\n x = x shr 6\n self.A2[x].clearBit(y)\n if self.A2[x] != 0:return\n y = x and (0b111111)\n x = x shr 6\n self.A1[x].clearBit(y)\n if self.A1[x] != 0:return\n y = x and (0b111111)\n x = x shr 6\n self.A0.clearBit(y)\n\n\n proc ge*(self:var WordsizeTree,x:int):int=\n var y = x and (0b111111)\n var x = x shr 6\n var t = self.A3[x] and (bitnot(0u) shl y)\n if t != 0:\n return (x shl 6) or (t.firstSetBit()-1)\n \n y = (x and (0b111111))+1\n x = x shr 6\n t = self.A2[x] and (bitnot(0u) shl y)\n if y != 64 and t != 0:\n x = (x shl 6) or (t.firstSetBit()-1)\n return (x shl 6) or (self.A3[x].firstSetBit()-1)\n \n y = (x and (0b111111))+1\n x = x shr 6\n t = self.A1[x] and (bitnot(0u) shl y)\n if y != 64 and t != 0:\n x = (x shl 6) or (t.firstSetBit()-1)\n x = (x shl 6) or (self.A2[x].firstSetBit()-1)\n return (x shl 6) or (self.A3[x].firstSetBit()-1)\n y = (x and (0b111111))+1\n x = x shr 6\n t = self.A0 and (bitnot(0u) shl y)\n if y != 64 and t != 0:\n x = (t.firstSetBit()-1)\n x = (x shl 6) or (self.A1[x].firstSetBit()-1)\n x = (x shl 6) or (self.A2[x].firstSetBit()-1)\n return (x shl 6) or (self.A3[x].firstSetBit()-1)\n return -1\n\n proc le*(self:var WordsizeTree,x:int):int=\n var y = 64-(x and (0b111111))-1\n var x = x shr 6\n var t = self.A3[x] and (bitnot(0u) shr y)\n if t != 0:\n return (x shl 6) or (t.fastLog2())\n y = 64-((x and (0b111111)))\n x = x shr 6\n t = self.A2[x] and (bitnot(0u) shr y)\n if y != 64 and t != 0:\n x = (x shl 6) or (t.fastLog2())\n return (x shl 6) or (self.A3[x].fastLog2())\n y = 64-((x and (0b111111)))\n x = x shr 6\n t = self.A1[x] and (bitnot(0u) shr y)\n if y != 64 and t != 0:\n x = (x shl 6) or (t.fastLog2())\n x = (x shl 6) or (self.A2[x].fastLog2())\n return (x shl 6) or (self.A3[x].fastLog2())\n y = 64-((x and (0b111111)))\n x = x shr 6\n t = self.A0 and (bitnot(0u) shr y)\n if y != 64 and t != 0:\n x = (t.fastLog2())\n x = (x shl 6) or (self.A1[x].fastLog2())\n x = (x shl 6) or (self.A2[x].fastLog2())\n return (x shl 6) or (self.A3[x].fastLog2())\n return -1"
# source: src/cplib/utils/mo.nim
ImportExpand "cplib/utils/mo" <=== "when not declared CPLIB_UTILS_MO:\n #{.checks: off.}\n const CPLIB_UTILS_MO* = 1\n import std/math\n import std/algorithm\n type Mo* = object\n width*: int\n N, Q: int\n qli: seq[seq[int]]\n size: int\n\n proc initMo*(N, Q: int, width = max(1, int(1.0 * float(N) / max(1.0, sqrt(float(Q) * 2.0 / 3.0))))): Mo =\n result.width = width\n result.N = N\n result.Q = Q\n let qlisize = N div width + 1\n result.qli = newSeq[seq[int]](qlisize)\n\n proc insert*(self: var Mo, l, r: int) =\n self.qli[l div self.width].add((r shl 40) or ((l) shl 20) or self.size)\n self.size += 1\n\n proc run*[AL, AR, DL, DR, REM](self: var Mo, add_left: AL, add_right: AR, delete_left: DL, delete_right: DR, rem: REM) =\n var nl = 0\n var nr = 0\n const mask2 = ((1 shl 20)-1) shl 20\n const mask3 = ((1 shl 20)-1)\n for i in 0..<len(self.qli):\n if len(self.qli[i]) == 0:\n continue\n sort(self.qli[i])\n if (i and 1) == 1:\n reverse(self.qli[i])\n for x in self.qli[i]:\n let ri = x shr 40\n let li = (x and mask2) shr 20\n let idx = x and mask3\n while nl > li: nl.dec; add_left(nl)\n while nr < ri: add_right(nr); nr.inc\n while nl < li: delete_left(nl); nl.inc\n while nr > ri: nr.dec; delete_right(nr)\n rem(idx)\n"
{.checks:off.}
var N,Q = ii()
var A = lii(N)
var cmp : seq[(int,int)]
for i in range(N):
cmp.add((A[i],i))
cmp.sort()
var rv = newseqwith(N,-1)
for i in range(N):
rv[cmp[i][1]] = i
var mos = initMo(N,Q)
var querys : seq[(int,int,int,char)]
for _ in range(Q):
var L,R,X = ii()
var c = si()[0]
L-=1
R-=1
querys.add((L,R,X,c))
mos.insert(L,R+1)
var st = initWordsizeTree()
var st2 = initWordsizeTree()
var cnt = newseqwith(10**7,0)
proc add_lr(l,r:int)=
var L = cmp[l][0]
var R = cmp[r][0]
if cnt[R-L] == 0:
st2.incl(R-L)
cnt[R-L] += 1
proc del_lr(l,r:int)=
var L = cmp[l][0]
var R = cmp[r][0]
if cnt[R-L] == 1:
st2.excl(R-L)
cnt[R-L] -= 1
proc ad(i:int)=
var x = rv[i]
var L = st.le(x)
var R = st.ge(x)
if L != -1 and R != -1:
del_lr(L,R)
add_lr(L,x)
add_lr(x,R)
elif R != -1:
add_lr(x,R)
elif L != -1:
add_lr(L,x)
st.incl(x)
proc de(i:int)=
var x = rv[i]
st.excl(x)
var L = st.le(x)
var R = st.ge(x)
if L != -1 and R != -1:
add_lr(L,R)
del_lr(L,x)
del_lr(x,R)
elif R != -1:
del_lr(x,R)
elif L != -1:
del_lr(L,x)
var ans = newseqwith(Q,-1)
proc memo(qi:int)=
var (L,R,X,c) = querys[qi]
if c == 'L':
ans[qi] = st2.le(X)
else:
ans[qi] = st2.ge(X)
mos.run(ad,ad,de,de,memo)
echo ans.join("\n")