Problem p03202 (python)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng)//2
	#d = defaultdict(int)
	d = dict()
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		dels = []
		if a[i] < a[i+1]:
			last = a[i+1]
			continue

		j = a[i+1]
		for k in d.keys():
			if j < k:
				dels.append(k)

		while j > 0:
			if j in d and d[j] == x-1:
				#d[j] = 0
				dels.append(j)
				j -= 1
			else:
				break

		if j in d:
			d[j] += 1
		else:
			d[j] = 1

		for k in dels:
			del d[k]

		if 0 in d:
			valid = False
			break
		last = j

	if valid:
		ok = x
	else:
		ng = x
print(ok)

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng)//2
	#d = defaultdict(int)
	d = dict()
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		dels = []
		if a[i] < a[i+1]:
			last = a[i+1]
			continue

		for k in d.keys():
			if last < k:
				dels.append(k)

		j = a[i+1]
		while j > 0:
			if j in d and d[j] == x-1:
				d[j] = 0
				dels.append(j)
				j -= 1
			else:
				break

		if j in d:
			d[j] += 1
		else:
			d[j] = 1

		for k in dels:
			del d[k]

		if 0 in d:
			valid = False
			break

	if valid:
		ok = x
	else:
		ng = x
print(ok)

Buggy submission (verdict: Runtime Error):
from copy import copy
n = int(input())
a = list(map(int, input().split()))

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng+1)//2
	#d = defaultdict(int)
	d = dict()
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		dels = []
		if a[i] < a[i+1]:
			last = a[i+1]

		else:
			for k in d.keys():
				if last < k:
					dels.append(k)

			j = a[i+1]
			while j > 0:
				if j in d and d[j] == x-1:
					d[j] = 0
					dels.append(j)
					j -= 1
				else:
					break

			if j in d:
				d[j] += 1
			else:
				d[j] = 1

		for k in dels:
			del d[k]

		if 0 in d:
			valid = False
			break

	if valid:
		ok = x
	else:
		ng = x
print(ok)

Buggy submission (verdict: Runtime Error):
from copy import copy
n = int(input())
a = list(map(int, input().split()))

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng)//2
	#d = defaultdict(int)
	d = dict()
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		dels = []
		if a[i] < a[i+1]:
			last = a[i+1]

		else:
			for k in d.keys():
				if last < k:
					dels.append(k)

			j = a[i+1]
			while j > 0:
				if j in d and d[j] == x-1:
					d[j] = 0
					dels.append(j)
					j -= 1
				else:
					break

			if j in d:
				d[j] += 1
			else:
				d[j] = 1

		for k in dels:
			del d[k]

		if 0 in d:
			valid = False
			break

	if valid:
		ok = x
	else:
		ng = x
print(ok)

Buggy submission (verdict: Runtime Error):
from copy import copy
n = int(input())
a = list(map(int, input().split()))

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng)//2
	#d = defaultdict(int)
	d = dict()
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		dels = []
		if a[i] < a[i+1]:
			last = a[i+1]
		elif a[i] > a[i+1]:
			#dels = []
			for k in d.keys():
				if k > last:
					dels.append(k)
			if a[i+1] > last:
				d[a[i+1]] = 1
			else:
				j = a[i+1]
				while j in d:
					if d[j] != x-1 or j <= 0:
						break
					else:
						dels,append(j)
						j -= 1
				if j in d:
					d[j] += 1
				else:
					d[j] = 1
			last = a[i+1]
		elif a[i] == a[i+1]:
			#dels = []
			for k in d.keys():
				if k > last:
					dels.append(k)
			j = a[i+1]
			while j in d:
				if d[j] != x-1 or j <= 0:
					break
				else:
					dels.append(j)
					j -= 1
			if j in d:
				d[j] += 1
			else:
				d[j] = 1
			last = a[i+1]

		for k in dels:
			del d[k]

		if 0 in d:
			valid = False
			break

	if valid:
		ok = x
	else:
		ng = x
print(ok)

Buggy submission (verdict: Runtime Error):
from copy import copy
n = int(input())
a = list(map(int, input().split()))

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng)//2
	#d = defaultdict(int)
	d = dict()
	dels = []
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		if a[i] < a[i+1]:
			last = a[i+1]
		elif a[i] > a[i+1]:
			#dels = []
			for k in d.keys():
				if k > last:
					dels.append(k)
			if a[i+1] > last:
				d[a[i+1]] = 1
			else:
				j = a[i+1]
				while j in d:
					if d[j] != x-1 or j <= 0:
						break
					else:
						dels,append(j)
						j -= 1
				if j in d:
					d[j] += 1
				else:
					d[j] = 1
			last = a[i+1]
		elif a[i] == a[i+1]:
			#dels = []
			for k in d.keys():
				if k > last:
					dels.append(k)
			j = a[i+1]
			while j in d:
				if d[j] != x-1 or j <= 0:
					break
				else:
					dels.append(j)
					j -= 1
			if j in d:
				d[j] += 1
			else:
				d[j] = 1
			last = a[i+1]

		for k in dels:
			del d[k]

		if 0 in d:
			valid = False
			break

	if valid:
		ok = x
	else:
		ng = x
print(ok)

Buggy submission (verdict: Runtime Error):
from copy import copy
n = int(input())
a = list(map(int, input().split()))

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng)//2
	#d = defaultdict(int)
	d = dict()
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		if a[i] < a[i+1]:
			last = a[i+1]
		elif a[i] > a[i+1]:
			dels = []
			for k in d.keys():
				if k > last:
					dels.append(k)
			if a[i+1] > last:
				d[a[i+1]] = 1
			else:
				j = a[i+1]
				while j in d:
					if d[j] != x-1 or j <= 0:
						break
					else:
						dels,append(j)
						j -= 1
				if j in d:
					d[j] += 1
				else:
					d[j] = 1
			last = a[i+1]
		elif a[i] == a[i+1]:
			dels = []
			for k in d.keys():
				if k > last:
					dels.append(k)
			j = a[i+1]
			while j in d:
				if d[j] != x-1 or j <= 0:
					break
				else:
					dels.append(j)
					j -= 1
			if j in d:
				d[j] += 1
			else:
				d[j] = 1
			last = a[i+1]

		for k in dels:
			del d[k]

		if 0 in d:
			valid = False
			break

	if valid:
		ok = x
	else:
		ng = x
print(ok)

Buggy submission (verdict: Runtime Error):
#from collections import defaultdict
from copy import copy
n = int(input())
a = list(map(int, input().split()))

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng)//2
	#d = defaultdict(int)
	d = dict()
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		if a[i] > a[i+1]:
			if a[i+1] > last:
				d[a[i+1]] = 1
			else:
				j = a[i+1]
				while j in d:
					if d[j] != x-1 and j <= 0:
						break
					else:
						del d[j]
						j -= 1
				if j in d:
					d[j] += 1
				else:
					d[j] = 1
			last = a[i+1]
		elif a[i] == a[i+1]:
			j = a[i+1]
			while j in d:
				if d[j] != x-1 and j <= 0:
					break
				else:
					del d[j]
					j -= 1
			if j in d:
				d[j] += 1
			else:
				d[j] = 1
			last = a[i+1]

		e = copy(d)
		for k in d.keys():
			if k > last:
				del e[k]
		d = copy(e)

        if 0 in d:
			valid = False
			break


	if valid:
		ok = x
	else:
		ng = x
print(ok)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng)//2
	d = defaultdict(int)
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		if a[i] > a[i+1]:
			if a[i+1] > last:
				d[a[i+1]] = 1
			else:
				j = a[i+1]
				while d[j] == x-1 and j > 0:
					d[j] = 0
					j -= 1
				d[j] += 1
			last = a[i+1]
			for k in d.keys():
				if k > last:
					d.pop(k)
		elif a[i] == a[i+1]:
			j = a[i+1]
			while d[j] == x-1 and j > 0:
				d[j] = 0
				j -= 1
			d[j] += 1
			last = a[i+1]

		if d[0] > 0:
			valid = False
			break

	if valid:
		ok = x
	else:
		ng = x
print(ok)

Buggy submission (verdict: Runtime Error):
H, W, n = map(int, input().split())
obst = []
for _ in range(n):
	x, y = map(int, input().split())
	if x >= y:
		obst.append([x-1, y-1, x-y])

bothered = [1000000] * (H+1)

for i in range(len(obst)):
	h, w, gap = obst[i][0], obst[i][1], obst[i][2]
	bothered[gap+1] = min(bothered[gap+1], h+1)

obst.sort(key=lambda x: x[0])

for i in range(len(obst)):
	h, w, gap = obst[i][0], obst[i][1], obst[i][2]
	if gap == 0:
		continue
	if h < bothered[gap]:
		print(h)
		break

else:
	print(H)