제출 #1199744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199744		ofoz	Curtains (NOI23_curtains)	Pypy 3	9 / 100	1598 ms	142564 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(" "))
        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()
 

컴파일 시 표준 출력 (stdout) 메시지

Compiling 'curtains.py'...

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

=======

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