結果

問題 No.3582 部分和不等式
コンテスト
ユーザー 👑 p-adic
提出日時 2024-08-11 19:51:30
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 1,377 ms / 2,000 ms
コード長 4,110 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 367 ms
コンパイル使用メモリ 20,572 KB
実行使用メモリ 15,576 KB
最終ジャッジ日時 2026-07-03 20:58:41
合計ジャッジ時間 11,210 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

R,O=range,print

def rec_str(a):
	if not isinstance(a,list):return str(a)
	return "".join(["[",", ".join(rec_str(x)for x in a),"]"])
class dliterator:
	def __init__(self,a,i):
		self.a,self.i=a,i
	def __eq__(self,i):
		return id(self.a)==id(i.a)and self.i==i.i
	def get(self):
		assert(self.i)
		return self.a.a[self.i][0]
	def __str__(self):
		return rec_str(self.get())
	def set(self,x):
		assert(self.i)
		self.a.a[self.i][0]=x
	def copy(self):
		return dliterator(self.a,self.i)
	def next(self,c=1):
		for _ in R(c):
			self.i=self.a.a[self.i][2]
			assert(self.i>=0)
	def prev(self,c=1):
		for _ in R(c):
			self.i=self.a.a[self.i][1]
			assert(self.i>=0)
	def shift(c):
		if c<0:self.prev(-c)
		else:self.next(c)
	def __ladd__(self,c):
		self.shift(c)
	def __lsub__(self,c):
		self.shift(-c)
class dllist:
	def __init__(self,init=[]):
		n=len(init)
		self.a=[[n,n,0]]+[[x,i,i+2]for x,i in zip(init,R(n))]
		if n:self.a[0][2],self.a[-1][2]=1,0
		self.i=self.end()
	def list(self):
		a=[]
		i=self.begin()
		e=self.end()
		while i!=e:
			a+=[i.get()]
			i.next()
		return a
	def __str__(self):
		return rec_str(self.list())
	def copy(self):
		return dllist(self.list())
	def size(self):
		return self.a[0][0]
	def end(self):
		return dliterator(self,0)
	def rend(self):
		return self.end()
	def begin(self):
		n=self.end()
		n.next()
		return n
	def rbegin(self):
		n=self.rend()
		n.prev()
		return n
	def front(self):
		return self.begin().get()
	def back(self):
		return self.rbegin().get()
	def insert_between(self,i,j,x,c):
		assert(id(i.a)==id(self)==id(j.a)and self.a[i.i][2]>=0 and self.a[j.i][2]>=0)
		k=j.copy()
		for _ in R(c):
			self.a[0][0]+=1
			n=self.i.i
			v=[x,i.i,k.i]
			if n:
				assert(self.a[n][2]==-1)
				self.i.prev()
				self.a[n]=v
			else:
				n=len(self.a)
				self.a+=[v]
			self.a[i.i][2]=self.a[k.i][1]=n
			k=dliterator(self,n)
	def insert_front(self,i,x,c=1):
		j=i.copy()
		j.prev()
		self.insert_between(j,i,x,c)
	def insert_back(self,i,x,c=1):
		j=i.copy()
		j.next()
		self.insert_between(i,j,x,c)
	def push_front(self,x,c=1):
		self.insert_front(self.begin(),x,c)
	def push_back(self,x,c=1):
		self.insert_back(self.rbegin(),x,c)
	def __ladd__(self,a):
		for x in a:self.push_back(x)
	def erase(self,i):
		assert(self.size()and id(i.a)==id(self)and i.i and self.a[i.i][2]>=0)
		self.a[0][0]-=1
		m=i.copy()
		m.prev()
		l=i.copy()
		l.next()
		self.a[m.i][2],self.a[l.i][1]=l.i,m.i
		self.i,self.a[i.i][1]=i,self.i.i
		self.a[i.i][2]=-1
		return l
	def pop_front(self):
		self.erase(self.begin())
	def pop_back(self):
		self.erase(self.rbegin())
	def clear(self):
		self.a,self.i=[[0,0,0]],self.end()
	def merge(self,other):
		i=self.begin()
		e=self.end()
		while other.size():
			t=other.front()
			while i!=e:
				if t < i.get():
					self.insert_front(i,t)
					break
				else:i.next()
			else:self.push_back(t)
			other.pop_front()


J=lambda:input().split()
N,Q=map(int,J())
query=dllist()
for _ in R(Q):
	A,B,M=map(int,J())
	temp=1
	S=list(map(int,J()[1:]))
	T=list(map(int,J()[1:]))
	query.push_back([dllist(S),dllist(T),M])
while query.size():
	i=query.begin()
	e=query.end()
	temp=count=0
	while i!=e:
		q=i.get()
		S=q[0]
		T=q[1]
		while S.size()and T.size()and S.back()==T.back():
			S.pop_back()
			T.pop_back()
		b=1
		for j in R(2):
			s=T if j else S
			if s.size():
				if b:b=0
				if temp<s.back():
					temp=s.back()
					count=1
					i_copy0=i.copy()
					j_copy0=j
				elif temp==s.back():
					count=2
					i_copy1=i.copy()
					j_copy1=j
		if b:
			if 0>q[2]:i=query.erase(i)
			else:exit(O("Yes"))
		else:i.next()
	if count==1:query.erase(i_copy0)
	elif count==2:
		if j_copy0==j_copy1:query.erase(i_copy0);query.erase(i_copy1)
		else:
			q0=i_copy0.get()
			S0=q0[0]
			T0=q0[1]
			q1=i_copy1.get()
			S1=q1[0]
			T1=q1[1]
			if j_copy0:T0.pop_back()
			else:S0.pop_back()
			if j_copy1:T1.pop_back()
			else:S1.pop_back()
			if S0.size()+T0.size()<S1.size()+T1.size():
				S1.merge(S0)
				T1.merge(T0)
				q1[2]+=q0[2]
				query.erase(i_copy0)
			else:
				S0.merge(S1)
				T0.merge(T1)
				q0[2]+=q1[2]
				query.erase(i_copy1)
O("No")
0