Submission #1199745

#TimeUsernameProblemLanguageResultExecution timeMemory
1199745ofozCurtains (NOI23_curtains)Pypy 3
9 / 100
1600 ms142964 KiB
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%)

=======
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...