Submission #1199640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199640		ofoz	Curtains (NOI23_curtains)	Pypy 3	0 / 100	141 ms	48812 KiB

curtains

from sys import stdout, setrecursionlimit
from math import ceil, floor, sqrt, comb
from collections import deque

def solve():
    n, m, q = map(int, input().split(" "))
    seg = []

    end = dict()
    start = dict()

    for _ in range(m):
        a, b = map(int, input().split(" "))
        seg.append((a, b))
        end[a] = min(end.get(a, float('inf')), b)
        start[b] = max(end.get(b, -float('inf')), a)

    prfx = [0] * (n+1)
    cur = []

    for i in range(1, n+1):
        if i in end: cur.append(end[i])
        while cur and cur[-1] < i: cur.pop()
        prfx[i] = prfx[i-1]
        if cur: prfx[i] += 1
    
    def getPrfx(l: int, r: int):
        left = 0 if l == 0 else prfx[l-1]
        right = prfx[r]
        return right - left
    
    for _ in range(q):
        a, b = map(int, input().split(" "))
        s = getPrfx(a, b)
        if s < (b-a+1) or b not in end.values() or a not in end:
            print("NO")
        elif end[a] > b or start[b] < a:
            print("NO")
        else:
            print("YES")

    

                



solve()
 

Compilation message (stdout)

Compiling 'curtains.py'...

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

=======

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36
• Subtask 6: 0 / 20