Submission #61611260

---

Source Code Expand

from collections import defaultdict, deque, Counter
from functools import cache
# import copy
from itertools import combinations, permutations, product, accumulate, groupby, chain
from more_itertools import distinct_permutations
from heapq import heapify, heappop, heappush, heappushpop
import math
import bisect
# from pprint import pprint
from random import randint, shuffle, randrange
from sortedcontainers import SortedSet, SortedList, SortedDict
import sys
# sys.setrecursionlimit(2000000)
input = lambda: sys.stdin.readline().rstrip('\n')
inf = float('inf')
mod1 = 10**9+7
mod2 = 998244353
def ceil_div(x, y): return -(-x//y)

#################################################   

def parallel_binary_search():
    oks, ngs = [0]*Q, [(r-l)//2+1 for l, r in querys]
    while True:
        exit_flag = True
        events = []
        look = []
        for q, (l, r) in enumerate(querys):
            if abs(oks[q]-ngs[q]) > 1:
                look.append(q)
                exit_flag = False
                mid = (oks[q]+ngs[q])>>1
                events.append((l, q))
                events.append((l+mid, q))
        if exit_flag:
            return oks
        
        events.sort(key=lambda e: e[0])
        T = [0]*Q
        hq = []
        deled = set()
        ei = 0
        is_out = [False]*Q
        for i in range(N):
            while ei < len(events) and events[ei][0] == i:
                _, q = events[ei]
                l, r = querys[q]
                mid = (oks[q]+ngs[q])>>1
                if T[q] == 0:
                    heappush(hq, (r-mid-l, q))
                else:
                    deled.add(q)
                T[q] ^= 1
                ei += 1
            while hq and i+hq[0][0] >= N or hq and A[i]*2 > A[i+hq[0][0]]:
                _, q = heappop(hq)
                if q not in deled:
                    is_out[q] = True

        for q in look:
            mid = (oks[q]+ngs[q])>>1
            if is_out[q]:
                ngs[q] = mid
            else:
                oks[q] = mid

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
querys = []
for _ in range(Q):
    l, r = map(int, input().split())
    l -= 1
    querys.append((l, r))
print(*parallel_binary_search(), sep="\n")

Submission Info

Judge Result