結果

問題 No.274 The Wall
コンテスト
ユーザー ayaoni
提出日時 2020-12-28 11:39:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,176 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 347,936 KB
最終ジャッジ日時 2024-10-02 12:36:43
合計ジャッジ時間 4,605 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 3 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def LS2(): return list(sys.stdin.readline().rstrip())


class SCC:
    def __init__(self,N):
        self.N = N
        self.graph = [[] for _ in range(N)]
        self.graph_rev = [[] for _ in range(N)]
        self.flag = [False]*N

    def add_edge(self,start,end):
        if start == end:
            return
        self.graph[start].append(end)
        self.graph_rev[end].append(start)

    def dfs(self,node,graph):
        self.flag[node] = True
        for n in graph[node]:
            if self.flag[n]:
                continue
            self.dfs(n,graph)
        self.order.append(node)

    def first_dfs(self):
        self.flag = [False]*self.N
        self.order = []
        for i in range(self.N):
            if self.flag[i] == False:
                self.dfs(i,self.graph)

    def second_dfs(self):
        self.flag = [False]*self.N
        self.ans = []
        for n in reversed(self.order):
            if self.flag[n]:
                continue
            self.flag[n] = True
            self.order = []
            self.dfs(n,self.graph_rev)
            self.order.reverse()
            self.ans.append(self.order)

    def scc(self):
        self.first_dfs()
        self.second_dfs()
        return self.ans


class Two_SAT():
    def __init__(self,N):
        self.N = N
        self.e = [[] for _ in range(2*N)]

    def add_condition(self,start,bool_start,end,bool_end):  # start or end という条件を考える
        self.e[start*2+(bool_start^1)].append(end*2+bool_end)
        self.e[end*2+(bool_end^1)].append(start*2+bool_start)

    def satisfiable(self):
        scc = SCC(2*self.N)
        for i in range(2*self.N):
            for j in self.e[i]:
                scc.add_edge(i,j)
        C = scc.scc()
        I = [0]*(2*self.N)
        for i in range(len(C)):
            for j in C[i]:
                I[j] = i
        res = [0]*(2*self.N)
        for i in range(self.N):
            if I[2*i] == I[2*i+1]:
                return (False,res)
            if I[2*i] < I[2*i+1]:
                res[i] = 1
        return (True,res)


N,M = MI()
LR = [tuple(MI()) for _ in range(N)]


def is_intersect(A,B,C,D):  # [A,B],[C,D] が交わるか否か
    if B < C or D < A:
        return False
    return True


TS = Two_SAT(N)
for i in range(N-1):
    L0,R0 = LR[i]
    for j in range(i+1,N):
        L1,R1 = LR[j]
        for k in range(2):
            if k == 0:
                A,B = L0,R0
            else:
                A,B = M-1-R0,M-1-L0
            for l in range(2):
                if l == 0:
                    C,D = L1,R1
                else:
                    C,D = M-1-R1,M-1-L1
                if is_intersect(A,B,C,D):
                    TS.add_condition(i,k,j,l)

b,r = TS.satisfiable()
print('NYOE S'[b::2])
0