#1059516 (PyPy3) No.274 The Wall

• 問題: No.274 The Wall
• ユーザー: lam6er
• 提出日時: 2025-03-26 15:48:33
• 言語: PyPy3 (7.3.15)
• 結果: MLE
• 実行時間: -
• コード長: 3,651 bytes
• コンパイル時間: 1,175 ms
• コンパイル使用メモリ: 82,360 KB
• 実行使用メモリ: 856,276 KB
• 最終ジャッジ日時: 2025-03-26 15:49:31
• 合計ジャッジ時間: 6,714 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 4
other	AC * 8 MLE * 1 -- * 14

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
import sys
sys.setrecursionlimit(1 << 25)
def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    blocks = []
    for _ in range(N):
        L = int(input[ptr])
        ptr += 1
        R = int(input[ptr])
        ptr += 1
        o_l, o_r = L, R
        f_l = (M - 1) - R
        f_r = (M - 1) - L
        blocks.append(((o_l, o_r), (f_l, f_r)))
    
    size = 2 * N
    original_graph = [[] for _ in range(2 * N)]
    transposed_graph = [[] for _ in range(2 * N)]
    def overlaps(a1, a2, b1, b2):
        return a1 <= b2 and b1 <= a2
    for i in range(N):
        for j in range(i + 1, N):
            o_i = blocks[i][0]
            f_i = blocks[i][1]
            o_j = blocks[j][0]
            f_j = blocks[j][1]
            # Case 1: o_i and o_j
            if overlaps(o_i[0], o_i[1], o_j[0], o_j[1]):
                u = 2 * i
                v = 2 * j + 1
                original_graph[u].append(v)
                transposed_graph[v].append(u)
                u = 2 * j
                v = 2 * i + 1
                original_graph[u].append(v)
                transposed_graph[v].append(u)
            # Case 2: o_i and f_j
            if overlaps(o_i[0], o_i[1], f_j[0], f_j[1]):
                u = 2 * i
                v = 2 * j
                original_graph[u].append(v)
                transposed_graph[v].append(u)
                u = 2 * j + 1
                v = 2 * i + 1
                original_graph[u].append(v)
                transposed_graph[v].append(u)
            # Case 3: f_i and o_j
            if overlaps(f_i[0], f_i[1], o_j[0], o_j[1]):
                u = 2 * i + 1
                v = 2 * j + 1
                original_graph[u].append(v)
                transposed_graph[v].append(u)
                u = 2 * j
                v = 2 * i
                original_graph[u].append(v)
                transposed_graph[v].append(u)
            # Case 4: f_i and f_j
            if overlaps(f_i[0], f_i[1], f_j[0], f_j[1]):
                u = 2 * i + 1
                v = 2 * j
                original_graph[u].append(v)
                transposed_graph[v].append(u)
                u = 2 * j + 1
                v = 2 * i
                original_graph[u].append(v)
                transposed_graph[v].append(u)
    visited = [False] * (2 * N)
    order = []
    for u in range(2 * N):
        if not visited[u]:
            stack = [(u, False)]
            while stack:
                node, processed = stack.pop()
                if processed:
                    order.append(node)
                    continue
                if visited[node]:
                    continue
                visited[node] = True
                stack.append((node, True))
                for v in original_graph[node]:
                    if not visited[v]:
                        stack.append((v, False))
    visited = [False] * (2 * N)
    component = [0] * (2 * N)
    current = 0
    for node in reversed(order):
        if not visited[node]:
            stack = [node]
            visited[node] = True
            while stack:
                u = stack.pop()
                component[u] = current
                for v in transposed_graph[u]:
                    if not visited[v]:
                        visited[v] = True
                        stack.append(v)
            current += 1
    possible = True
    for i in range(N):
        if component[2 * i] == component[2 * i + 1]:
            possible = False
            break
    print("YES" if possible else "NO")
if __name__ == "__main__":
    main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX