Submission #1199745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199745		ofoz	Curtains (NOI23_curtains)	Pypy 3	9 / 100	1600 ms	142964 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 = []


    for _ in range(m):
        a, b = map(int, input().split(" "))
        a -= 1
        b -= 1
        seg.append((a, b))
    seg.sort()


    mn = [float('inf')] * n
    # print(seg)
    queries = []
    for i in range(q):
        a, b = map(int, input().split(" "))
        a -= 1
        b -= 1
        queries.append((a, b, i))
    queries.sort()
    queries.reverse()
    res = [0] * q
    for (a, b, i) in queries:
        while seg and seg[-1][0] >= a:
            aa, bb = seg.pop()
            for j in range(aa, bb+1): mn[j] = min(mn[j], bb)
        # print(a, b, mn)
        mx = -float('inf')
        for j in range(a, b+1): mx = max(mx, mn[j])
        if mx <= b:
            res[i] = "YES"
        else:
            res[i] = "NO"

    print(*res, sep = "\n")


    
"""
we need a data structure that will let us update a range and query for maximum.
segment tree: let the current node be the max
"""
                



solve()
 

Compilation message (stdout)

Compiling 'curtains.py'...

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

=======

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