結果
| 問題 | No.274 The Wall |
| ユーザー |
 vwxyz
|
| 提出日時 | 2023-05-17 02:04:19 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 5,476 bytes |
| コンパイル時間 | 334 ms |
| コンパイル使用メモリ | 87,208 KB |
| 実行使用メモリ | 839,408 KB |
| 最終ジャッジ日時 | 2023-08-21 12:05:11 |
| 合計ジャッジ時間 | 6,016 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 94 ms
72,340 KB |
| testcase_01 | AC | 96 ms
72,324 KB |
| testcase_02 | AC | 99 ms
72,280 KB |
| testcase_03 | MLE | - |
| testcase_04 | AC | 101 ms
71,788 KB |
| testcase_05 | AC | 95 ms
72,332 KB |
| testcase_06 | AC | 100 ms
72,260 KB |
| testcase_07 | AC | 93 ms
72,408 KB |
| testcase_08 | AC | 96 ms
72,212 KB |
| testcase_09 | AC | 97 ms
72,160 KB |
| testcase_10 | AC | 96 ms
72,164 KB |
| testcase_11 | MLE | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
ソースコード
import sys
readline=sys.stdin.readline
from collections import defaultdict
class Prime:
def __init__(self,N):
assert N<=10**8
self.smallest_prime_factor=[None]*(N+1)
for i in range(2,N+1,2):
self.smallest_prime_factor[i]=2
n=int(N**.5)+1
for p in range(3,n,2):
if self.smallest_prime_factor[p]==None:
self.smallest_prime_factor[p]=p
for i in range(p**2,N+1,2*p):
if self.smallest_prime_factor[i]==None:
self.smallest_prime_factor[i]=p
for p in range(n,N+1):
if self.smallest_prime_factor[p]==None:
self.smallest_prime_factor[p]=p
self.primes=[p for p in range(N+1) if p==self.smallest_prime_factor[p]]
def Factorize(self,N):
assert N>=1
factors=defaultdict(int)
if N<=len(self.smallest_prime_factor)-1:
while N!=1:
factors[self.smallest_prime_factor[N]]+=1
N//=self.smallest_prime_factor[N]
else:
for p in self.primes:
while N%p==0:
N//=p
factors[p]+=1
if N<p*p:
if N!=1:
factors[N]+=1
break
if N<=len(self.smallest_prime_factor)-1:
while N!=1:
factors[self.smallest_prime_factor[N]]+=1
N//=self.smallest_prime_factor[N]
break
else:
if N!=1:
factors[N]+=1
return factors
def Divisors(self,N):
assert N>0
divisors=[1]
for p,e in self.Factorize(N).items():
pow_p=[1]
for _ in range(e):
pow_p.append(pow_p[-1]*p)
divisors=[i*j for i in divisors for j in pow_p]
return divisors
def Is_Prime(self,N):
return N==self.smallest_prime_factor[N]
def Totient(self,N):
for p in self.Factorize(N).keys():
N*=p-1
N//=p
return N
def Mebius(self,N):
fact=self.Factorize(N)
for e in fact.values():
if e>=2:
return 0
else:
if len(fact)%2==0:
return 1
else:
return -1
def SCC(N,edges):
start = [0] * (N + 1)
elist = [0] * len(edges)
for e in edges:
start[e[0] + 1] += 1
for i in range(1, N + 1):
start[i] += start[i - 1]
counter = start[:]
for e in edges:
elist[counter[e[0]]] = e[1]
counter[e[0]] += 1
N = N
now_ord = group_num = 0
visited = []
low = [0] * N
order = [-1] * N
ids = [0] * N
parent = [-1] * N
stack = []
for i in range(N):
if order[i] == -1:
stack.append(i)
stack.append(i)
while stack:
v = stack.pop()
if order[v] == -1:
low[v] = order[v] = now_ord
now_ord += 1
visited.append(v)
for i in range(start[v], start[v + 1]):
to = elist[i]
if order[to] == -1:
stack.append(to)
stack.append(to)
parent[to] = v
else:
low[v] = min(low[v], order[to])
else:
if low[v] == order[v]:
while True:
u = visited.pop()
order[u] = N
ids[u] = group_num
if u == v:
break
group_num += 1
if parent[v] != -1:
low[parent[v]] = min(low[parent[v]], low[v])
for i, x in enumerate(ids):
ids[i] = group_num - 1 - x
groups = [[] for _ in range(group_num)]
for i, x in enumerate(ids):
groups[x].append(i)
return groups
class TwoSAT:
def __init__(self,N):
self.N=N
self.edges=[]
def Add_Clause(self,i,f,j,g):
assert 0<=i<self.N
assert 0<=j<self.N
self.edges.append((2*i+(0 if f else 1),2*j+(1 if g else 0)))
self.edges.append((2*j+(0 if g else 1),2*i+(1 if f else 0)))
def Satisfiable(self):
scc=SCC(2*self.N,self.edges)
idx=[None]*2*self.N
for i,lst in enumerate(scc):
for x in lst:
idx[x]=i
retu=[None]*self.N
for i in range(self.N):
if idx[2*i]==idx[2*i+1]:
return None
retu[i]=idx[2*i]<idx[2*i+1]
return retu
N,M=map(int,readline().split())
L,R=[],[]
for n in range(N):
l,r=map(int,readline().split())
r+=1
L.append(l)
R.append(r)
TSAT=TwoSAT(N)
for i in range(N):
for j in range(i+1,N):
for bi in (0,1):
if bi==0:
li,ri=L[i],R[i]
else:
li,ri=M-R[i],M-L[i]
for bj in (0,1):
if bj==0:
lj,rj=L[j],R[j]
else:
lj,rj=M-R[j],M-L[j]
if max(li,lj)<min(ri,rj):
TSAT.Add_Clause(i,bi^1,j,bj^1)
if TSAT.Satisfiable():
ans="YES"
else:
ans="NO"
print(ans)