結果
問題 | No.905 Sorted? |
ユーザー |
![]() |
提出日時 | 2019-10-11 22:02:33 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 610 ms / 2,000 ms |
コード長 | 1,719 bytes |
コンパイル時間 | 79 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 26,884 KB |
最終ジャッジ日時 | 2024-11-25 07:30:02 |
合計ジャッジ時間 | 7,106 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
from collections import defaultdict,deque import sys,heapq,bisect,math,itertools,string,queue,copy,time sys.setrecursionlimit(10**8) INF = float('inf') mod = 10**9+7 eps = 10**-7 def inp(): return int(sys.stdin.readline()) def inpl(): return list(map(int, sys.stdin.readline().split())) def inpl_str(): return list(sys.stdin.readline().split()) class UnionFind: def __init__(self,N): # 頂点数 N self.table = [i for i in range(N)] # 親 table[x] == x で根 self.rank = [1 for i in range(N)] # 木の長さ self.size = [1 for i in range(N)] # 集合のサイズ def Find(self,x): #xの根を返す if self.table[x] == x: return x else: self.table[x] = self.Find(self.table[x]) #親の更新 self.size[x] = self.size[self.table[x]] return self.table[x] def Unite(self,x,y): x,y = self.Find(x), self.Find(y) sx,sy = self.Size(x), self.Size(y) if x == y: return if self.rank[x] > self.rank[y]: self.table[y] = x self.size[x] = sx + sy else: self.table[x] = y self.size[y] = sx + sy if self.rank[x] == self.rank[y]: self.rank[y] += 1 def Check(self,x,y): return self.Find(x) == self.Find(y) def Size(self,x): return self.size[self.Find(x)] N = inp() AA = inpl() UF_f = UnionFind(N) UF_g = UnionFind(N) for i in range(1,N): if AA[i-1] <= AA[i]: UF_f.Unite(i-1,i) if AA[i-1] >= AA[i]: UF_g.Unite(i-1,i) Q = inp() for q in range(Q): l,r = inpl() f = 1 if UF_f.Check(l,r) else 0 g = 1 if UF_g.Check(l,r) else 0 print(f,g)