Submission #1204144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204144		ofoz	Gift Exchange (JOI24_ho_t4)	Pypy 3	0 / 100	419 ms	71108 KiB

Main

from collections import deque
from sys import setrecursionlimit


def solve():
    n = int(input())
    a = list(map(int, input().split(" ")))
    b = list(map(int, input().split(" ")))


    def query(l: int, r: int):
        A = sorted(a[l:r+1])
        B = sorted(b[l:r+1])
        cur = 0
        sub = False
        while A or B:
            t1 = -1 if not A else A[-1]
            t2 = float('inf') if not B else B[-1]
            if t1 >= t2:
                A.pop()
                cur += 1
                sub = False
                continue

            if cur > 1 or (cur == 1 and sub):
                cur -= 1
                sub = True
                B.pop()
                continue
            return False
        if B: return False
        return True

    c = [0] * n
    for i in range(n):
        r = True
        if i != 0: r = a[i-1] < b[i]
        if i != n-1: r &= a[i] < b[i+1]

        c[i] = r

    prfx = [0] * n
    prfx[0] = c[0]
    for i in range(1, n):
        prfx[i] = prfx[i-1] + c[i]
    
    def getPrfx(l: int, r: int):
        left = 0 if l == 0 else prfx[l-1]
        right = prfx[r]
        return right - left

    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split(" "))
        l -= 1
        r -= 1
        res = getPrfx(l, r)
        print("Yes" if not res else "No")









solve()

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 38%)

=======

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 10
• Subtask 4: 0 / 31
• Subtask 5: 0 / 8
• Subtask 6: 0 / 12
• Subtask 7: 0 / 18
• Subtask 8: 0 / 12