Submission #1199744

#TimeUsernameProblemLanguageResultExecution timeMemory
1199744ofozCurtains (NOI23_curtains)Pypy 3
9 / 100
1598 ms142564 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 = []

    end = dict()
    start = dict()

    for _ in range(m):
        a, b = map(int, input().split(" "))
        a -= 1
        b -= 1
        seg.append((a, b))
        end[a] = min(end.get(a, float('inf')), b)
        start[b] = max(end.get(b, -float('inf')), a)
    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)
        if max(mn[a:b+1]) <= 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 33%)

=======
#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...