Language: C++

#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)
# 偏り対策

import sys
from collections import deque
from functools import lru_cache
from math import floor, log2


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        # print(mid, i, j, ps[i][dim], ps[j][dim])
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=lambda p: p[dim])):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    # while t - s > 100:
    #     i = partition(ps, s, t, dim)
    #     if i > mid:
    #         t = i - 1
    #     elif i < mid:
    #         s = i + 1
    #     else:
    #         return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, _dim):
    n = len(ps)
    q = deque([(0, n-1, 0)])
    while len(q) > 0:
        s, t, lv = q.popleft()
        mid = halve(ps, s, t, _dim(lv))
        if t - s < 100:
            continue
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, _dim, s, t):
    n = len(ps)
    stack = [(0, n-1, 0)]
    ret = []
    while len(stack) > 0:
        i, j, lv = stack.pop()
        dim = _dim(lv)
        mid = (i+j) // 2
        left, right = t[dim] < ps[mid][dim], s[dim] > ps[mid][dim]
        if j - i < 100:
            if left:
                j = mid-1
            elif right:
                i = mid+1
            ret.extend([p[2] for p in ps[i:j+1]
                        if (s[0] <= p[0] <= t[0] and
                            s[1] <= p[1] <= t[1])])
            continue

        if left:
            stack.append((i, mid-1, lv+1))
        elif right:
            stack.append((mid+1, j, lv+1))
        else:
            if s[0] <= ps[mid][0] <= t[0] and s[1] <= ps[mid][1] <= t[1]:
                ret.append(ps[mid][2])
            stack.append((i, mid-1, lv+1))
            stack.append((mid+1, j, lv+1))

    return ret


def dimension(ps):
    @lru_cache(maxsize=len(ps))
    def _dimension(lv):
        return pat[lv % len(pat)]

    xs = [p[0] for p in ps]
    ys = [p[1] for p in ps]

    cx = len(set(xs))
    cy = len(set(ys))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(len(ps))))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(len(ps))))

    pat = []
    for i in range(ratio):
        pat.append(m)
    pat.append(s)

    return _dimension


def run():
    n = int(input())
    ps = []
    i = 0
    for line in sys.stdin:
        if i < n:
            x, y = [int(v) for v in line.split()]
            ps.append((x, y, i))
            i += 1
        else:
            break

    dim = dimension(ps)
    build(ps, dim)

    # q = int(line)
    # fmt = "{}\n"
    for line in sys.stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        # s = "".join([fmt.format(id_) for id_ in sorted(search(ps, dim, (sx, sy), (tx, ty)))])
        s = "".join([f"{id_}\n" for id_ in sorted(search(ps, dim, (sx, sy), (tx, ty)))])
        sys.stdout.write(s + "\n")


if __name__ == '__main__':
    run()



Compiler output:
a.cc:1:2: error: invalid preprocessing directive #!
    1 | #!/usr/bin/env pypy3
      |  ^
a.cc:2:3: error: invalid preprocessing directive #DSL_2_C
    2 | # DSL_2_C: Range Search(kD Tree)
      |   ^~~~~~~
a.cc:3:3: error: invalid preprocessing directive #\U0000504f\U0000308a\U00005bfe\U00007b56
    3 | # 偏り対策
      |   ^~~~~~~~
a.cc:36:11: error: invalid preprocessing directive #print
   36 |         # print(mid, i, j, ps[i][dim], ps[j][dim])
      |           ^~~~~
a.cc:56:7: error: invalid preprocessing directive #while
   56 |     # while t - s > 100:
      |       ^~~~~
a.cc:57:11: error: invalid preprocessing directive #i; did you mean #if?
   57 |     #     i = partition(ps, s, t, dim)
      |           ^
      |           if
a.cc:58:21: error:  ':' without preceding '?'
   58 |     #     if i > mid:
      |                     ^
a.cc:60:23: error:  ':' without preceding '?'
   60 |     #     elif i < mid:
      |                       ^
a.cc:62:15: warning: extra tokens at end of #else directive [-Wendif-labels]
   62 |     #     else:
      |               ^
a.cc:63:15: error: invalid preprocessing directive #return
   63 |     #         return mid
      |               ^~~~~~
a.cc:116:5: error: stray '@' in program
  116 |     @lru_cache(maxsize=len(ps))
      |     ^
a.cc:156:7: error: invalid preprocessing directive #q
  156 |     # q = int(line)
      |       ^
a.cc:157:7: error: invalid preprocessing directive #fmt
  157 |     # fmt = "{}\n"
      |       ^~~
a.cc:160:11: error: invalid preprocessing directive #s
  160 |         # s = "".join([fmt.format(id_) for id_ in sorted(search(ps, dim, (sx, sy), (tx, ty)))])
      |           ^
a.cc:165:16: warning: multi-character literal with 8 characters exceeds 'int' size of 4 bytes
  165 | if __name__ == '__main__':
      |                ^~~~~~~~~~
a.cc:58: error: unterminated #else
   58 |     #     if i > mid:
a.cc:5:1: error: 'import' does not name a type
    5 | import sys
      | ^~~~~~
a.cc:5:1: note: C++20 'import' only available with '-fmodules-ts'