Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03061 (python)

Fixed submission:
class Segtree(object):
    def __init__(self,A,f,u):
        n=2**(len(A).bit_length())
        N=2*n-1
        self.__num=n
        self.__len=N
        self.__seg=[u]*N
        self.__f=f
        self.__u=u
        # init
        for i in range(len(A)): # set
            self.__seg[n+i-1]=A[i]
        for i in range(n-2,-1,-1): # built, iの子のnodeは2i+1,2i+2
            self.__seg[i]=f(self.__seg[2*i+1],self.__seg[2*i+2])

    def __repr__(self):
        return str(self.__seg)

    def get_tree(self):
        return self.__seg

    def update(k,v):
        "A[k]=v"
        k+=self.__num-1
        self.__seg[k]=v
        while k+1: # k=0の処理が終わったら-1になってる
            k=(k-1)//2 # kの親のnodeは(k-1)//2
            self.__seg[k]=self.__f(self.__seg[k*2+1],self.__seg[k*2+2])

    def query(self,p,q): # reduce(f,A[p:q])
        if q<=p: return self.__u
        p+=self.__num-1
        q+=self.__num-2
        res=self.__u
        while q-p>1:
            if p&1==0:
                res=self.__f(res,self.__seg[p])
            if q&1==1:
                res=self.__f(res,self.__seg[q])
                q-=1
            p=p//2
            q=(q-1)//2
        if p==q: res=self.__f(res,self.__seg[p])
        else: res=self.__f(self.__f(res,self.__seg[p]),self.__seg[q])
        return res


def resolve():
    from fractions import gcd
    n=int(input())
    A=list(map(int,input().split()))
    if n==2:
        print(max(A))
        return
    seg=Segtree(A,gcd,0)
    ans=0
    for i in range(n):
        ans=max(ans,gcd(seg.query(0,i),seg.query(i+1,n)))
    print(ans)

resolve()

Buggy submission (verdict: Runtime Error):
from fractions import gcd
from functools import reduce
def resolve():
    n=int(input())
    A=set(map(int,input().split()))
    ans=0
    if n==2:
        print(max(A))
        return
    for a in A:
        ans=max(ans,reduce(gcd,A^{a}))
    print(ans)
resolve()

Buggy submission (verdict: Runtime Error):
from fractions import gcd
def resolve():
    n=int(input())
    A=set(map(int,input().split()))
    ans=0
    if n==2:
        print(max(A))
        return
    for a in A:
        ans=max(ans,gcd(*(A^{a})))
    print(ans)
resolve()

Buggy submission (verdict: Runtime Error):
def resolve():
    from math import gcd
    #%%
    n=int(input())
    A=set(map(int,input().split()))
    ans=0
    if n==2:
        print(max(A))
        return
    for a in A:
        ans=max(ans,gcd(*(A^{a})))
    print(ans)
resolve()
Problem p03148 (python)

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from heapq import heappop,heappush
    n,k=map(int,input().split())
    A=[0]*n
    for i in range(n):
        t,d=map(int,input().split())
        t-=1
        A[i]=(t,d)
    A.sort(lambda x:-x[1]) # d の降順ソート

    # 各種の中で最大かどうかをわける
    B=[0]*n
    first=[1]*n
    for i,a in enumerate(A):
        t,d=a
        if(first[t]):
            first[t]=0
            B[i]=(d,1)
        else:
            B[i]=(d,0)

    # 初めは貪欲に d の大きい方から k 個取る
    S=[]
    for i in range(k):
        d,f=B[i]
        heappush(S,(f,d))
    x=sum(S[i][1] for i in range(k))
    y=sum(S[i][0] for i in range(k))
    ans=x+y*y

    # 残りの n-k について、Sからf=0で最小のものを捨て、B[k:]からf=1の中で最大のものを加える
    B=B[k:]
    for i in range(n-k):
        d,f=B[i]
        if(f==0): continue
        pf,pd=heappop(S)
        if(pf==1): break
        x+=d-pd
        y+=1
        ans=max(ans,x+y*y)
    print(ans)
resolve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from heapq import heappop,heappush
    n,k=map(int,input().split())
    A=[0]*n
    for i in range(n):
        t,d=map(int,input().split())
        t-=1
        A[i]=(t,d)
    A.sort(lambda x:-x[1]) # d の降順ソート

    # 各種の中で最大かどうかをわける
    B=[0]*n
    first=[1]*n
    for i,a in enumerate(A):
        t,d=a
        if(first[t]):
            first[t]=0
            B[i]=(d,1)
        else:
            B[i]=(d,0)

    # 初めは貪欲に d の大きい方から k 個取る
    S=[]
    for i in range(k):
        d,f=B[i]
        heappush(S,(f,d))
    x=sum(S[i][1] for i in range(k))
    y=sum(S[i][0] for i in range(k))
    ans=x+y*y

    # 残りの n-k について、Sからf=0で最小のものを捨て、B[k:]からf=1の中で最大のものを加える
    B=B[k:]
    for i in range(n-k):
        d,f=B[i]
        if(f==0): continue
        pf,pd=heappop(S)
        if(pf==1): break
        x+=d-pd
        y+=1
        ans=max(ans,x+y*y)
    print(ans)
resolve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from heapq import heappop,heappush,heapify
    n,k=map(int,input().split())
    A=[0]*n
    for i in range(n):
        t,d=map(int,input().split())
        t-=1
        A[i]=(t,d)
    A.sort(lambda x:-x[1]) # d の降順ソート

    # 各種の中で最大かどうかをわける
    B=[0]*n
    first=[1]*n
    for i,a in enumerate(A):
        t,d=a
        if(first[t]):
            first[t]=0
            B[i]=(d,1)
        else:
            B[i]=(d,0)

    # 初めは貪欲に d の大きい方から k 個取る
    S=[]
    for i in range(k):
        d,f=B[i]
        heappush(S,(f,d))
    x=sum(S[i][1] for i in range(k))
    y=sum(S[i][0] for i in range(k))
    ans=x+y*y

    # 残りの n-k について、Sからf=0で最小のものを捨て、B[k:]からf=1の中で最大のものを加える
    B=B[k:]
    for i in range(n-k):
        d,f=B[i]
        if(f==0): continue
        pf,pd=heappop(S)
        if(pf==1): break
        x+=d-pd
        y+=1
        ans=max(ans,x+y*y)
    print(ans)
resolve()
Problem p03164 (python)

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,W=map(int,input().split())
    w,v=[0]*n,[0]*n
    for i in range(n):
        w[i],v[i]=map(int,input().split())
    V=sum(v)
    dp=[INF]*(V+1)
    dp[0]=0
    for i in range(n):
        newdp=dp[:]
        for x in range(V+1):
            if(x+v[i]<V+1):
                newdp[x+v[i]]=min(newdp[x+v[i]],dp[x]+w[i])
        dp=newdp
    for i in range(V,-1,-1):
        if(dp[i]<=W):
            print(i)
            return
resolve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,w=map(int,input().split())
    W=[0]*(n+1); V=[0]*(n+1)
    for i in range(1,n+1):
        a,b=map(int,input().split())
        W[i]=a; V[i]=b
    # dp[i][c] iまでの品物で、重さがc以下
    dp=[[-1]*(w+1) for _ in range(n+1)]
    # メモ化再帰
    def solve(i,c):
        if(dp[i][c]!=-1): return dp[i][c]
        if(i==0):
            dp[i][c]=0
            return dp[i][c];
        if(c-W[i]>=0):
            dp[i][c]=max(solve(i-1,c-W[i])+V[i],solve(i-1,c))
            return dp[i][c]
        else:
            dp[i][c]=solve(i-1,c)
            return dp[i][c]
    print(solve(n,w))
resolve()
Problem p03171 (python)

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    dp = [[None] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][i] = 0

    for width in range(1, n + 1):
        for l in range(n):
            r = l + width
            if r > n:
                break
            turn = (n - (r - l)) & 1
            if turn & 1 == 0:
                dp[l][r] = max(A[l] + dp[l + 1][r], A[r - 1] + dp[l][r - 1])
            else:
                dp[l][r] = min(-A[l] + dp[l + 1][r], -A[r - 1] + dp[l][r - 1])


    print(dp[0][n])
resolve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    dp=[[None]*(n+1) for _ in range(n+1)]

    def dfs(l,r)->NoneType:
        if(dp[l][r] is not None): return
        if(l==r):
            dp[l][r]=0
            return

        # 1個先の値を確定させておく
        dfs(l+1,r)
        dfs(l,r-1)
        turn=(n-(r-l))%2
        if(turn==0): dp[l][r]=max(dp[l+1][r]+A[l],dp[l][r-1]+A[r-1])
        else: dp[l][r]=min(dp[l+1][r]-A[l],dp[l][r-1]-A[r-1])

    dfs(0,n)
    print(dp[0][n])
resolve()
Problem p03174 (python)

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    popcount_to_state = [[] for _ in range(n + 1)]
    for U in range(1 << n):
        popcount_to_state[bin(U).count('1')].append(U)

    dp = [0] * (1 << n)
    dp[0] = 1
    for i in range(n):
        A = tuple(map(int, input().split()))
        for j in range(n):
            if not A[j]:
                continue
            for U in popcount_to_state[i]:
                if (U >> j) & 1:
                    continue
                nU = U | 1 << j
                dp[nU] += dp[U]
                if dp[nU] >= MOD:
                    dp[nU] -= MOD
    print(dp[-1])
resolve()

Buggy submission (verdict: Runtime Error):
n = int(input())
dp = [None] * (1 << n)
dp[0] = 1
now = [0]
for _ in range(n):
    A = list(map(int, input().split()))
    next = []
    for i in range(n):
        if not A[i]:
            continue
        for U in now:
            if (U >> i) & 1:
                continue
            nU = U | 1 << i
            if dp[nU] is None:
                dp[nU] = dp[U]
                next.append(nU)
            else:
                dp[nU] += dp[U]
                if dp[nU] >= MOD:
                    dp[nU] -= MOD
    now = next

res = dp[-1]
if res is None:
    res = 0
print(res)

Buggy submission (verdict: Runtime Error):
from sys import stdin
input = lambda:stdin.buffer.readline().rstrip()
n = int(input())

dp = [None] * (1 << n)
dp[0] = 1
now = [0]
for _ in range(n):
    A = list(map(int, input().split()))
    next = []
    for i in range(n):
        if not A[i]:
            continue
        for U in now:
            if (U >> i) & 1:
                continue
            nU = U | 1 << i
            if dp[nU] is None:
                dp[nU] = dp[U]
                next.append(nU)
            else:
                dp[nU] += dp[U]
                if dp[nU] >= MOD:
                    dp[nU] -= MOD
    now = next

res = dp[-1]
if res is None:
    res = 0
print(res)
Problem p03184 (python)

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self,n):
        fact=[1]*(n+1); invfact=[1]*(n+1)
        for i in range(1,n+1): fact[i]=i*fact[i-1]%MOD
        invfact[n]=pow(fact[n],MOD-2,MOD)
        for i in range(n-1,-1,-1): invfact[i]=invfact[i+1]*(i+1)%MOD
        self.__fact=fact; self.__invfact=invfact

    def inv(self,n):
        assert(n>0)
        return self.__fact[n-1]*self.__invfact[n]%MOD

    def fact(self,n):
        return self.__fact[n]

    def invfact(self,n):
        return self.__invfact[n]

    def comb(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[k]*self.__invfact[n-k]%MOD

    def perm(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[n-k]%MOD

def resolve():
    h,w,n=map(int,input().split())
    RC=[None]*n
    for i in range(n):
        r,c=map(int,input().split())
        r-=1; c-=1
        RC[i]=(r,c)
    RC.append((h-1,w-1))
    n+=1
    RC.sort(lambda p:sum(p))

    mf=modfact(h+w)
    f=lambda x,y:mf.comb(x+y,x)
    dp=[None]*n
    for i in range(n):
        r,c=RC[i]
        res=f(r,c)
        for j in range(i):
            r0,c0=RC[j]
            res-=dp[j]*f(r-r0,c-c0)
        dp[i]=res%MOD

    print(dp[-1])
resolve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def modfact(n):
    fact=[1]*(n+1)
    invfact=[1]*(n+1)
    for i in range(1,n+1):
        fact[i]=i*fact[i-1]%MOD
    invfact[n]=pow(fact[n],MOD-2,MOD)
    for i in range(n-1,-1,-1):
        invfact[i]=invfact[i+1]*(i+1)%MOD
    return fact,invfact

def resolve():
    h,w,n=map(int,input().split())
    R=[(1,1),(h,w)]+[tuple(map(int,input().split())) for _ in range(n)]
    R.sort()
    n+=1
    dp=[[0]*2 for _ in range(n+1)]
    dp[0][0]=1
    fact,invfact=modfact(2000)
    for i in range(n):
        x,y=R[i]
        for j in range(i+1,n+1):
            dx=R[j][0]-x
            dy=R[j][1]-y
            if(dx<0 or dy<0): continue
            for m in range(2):
                dp[j][1-m]+=dp[i][m]*fact[dx+dy]*invfact[dx]*invfact[dy]
                dp[j][1-m]%=MOD
    print(dp[n][1]-dp[n][0])
resolve()
Problem p03239 (python)

Fixed submission:
N,T = map(int,input().split())
score = 1001
for i in range(N):
    c,t = map(int,input().split())
    if t<=T: score = min(score,c)
        
print("TLE" if score==1001 else score)

Buggy submission (verdict: Runtime Error):
import math
N,T = map(int,input().split())
score = math.inf
for i in range(N):
    c,t = map(int,input().split())
    if t<=T: score = min(score,c)
        
print("TLE" if score==math.inf else score)
Problem p03309 (python)

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=map(int,input().split())
    B=[a-i for i,a in enumerate(A)]
    if n==1:
        print(0)
        return
    B.sort()
    f=lambda x:sum(abs(x-b) for b in B)
    ans=min(f(B[n//2]),f(B[n//2+1]))
    print(ans)
resolve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=map(int,input().split())
    B=[a-i for i,a in enumerate(A)]
    B.sort()
    f=lambda x:sum(abs(x-b) for b in B)
    ans=min(f(B[n//2]),f(B[n//2+1]))
    print(ans)
resolve()
Problem p03343 (python)

Fixed submission:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from itertools import groupby
from heapq import heappop, heappush, heapify
def resolve():
    n, k, q = map(int, input().split())
    A = list(map(int, input().split()))

    ans = INF
    for m in sorted(A):
        C = []
        for key, it in groupby(A, key = lambda a : a >= m):
            if key is False:
                continue
            D = list(it)
            if len(D) >= k:
                D.sort()
                C.append(D[:len(D) - k + 1][::-1])

        if sum(len(a) for a in C) < q:
            continue
        heap = [(C[i].pop(), i) for i in range(len(C))]
        heapify(heap)
        for _ in range(q):
            M, i = heappop(heap)
            if C[i]:
                heappush(heap, (C[i].pop(), i))
        ans = min(ans, M - m)

    print(ans)
resolve()

Buggy submission (verdict: Runtime Error):
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from itertools import groupby
def resolve():
    n, k, q = map(int, input().split())
    A = list(map(int, input().split()))
    B = sorted(A)

    ans = INF
    for i, m in enumerate(B):
        score = 0
        for key, it in groupby([a >= m for a in A]):
            if key is False:
                continue
            l = sum(1 for _ in it)
            score += max(0, l - k + 1)

        if score >= q:
            ans = min(ans, B[i + q - 1] - m)

    print(ans)
resolve()
Problem p03386 (python)

Fixed submission:
a,b,k = map(int,input().split())
s = set(range(a,a+k))
t = set(range(b-k+1,b+1))
u = sorted(s|t)
for i in u:
    if a<=i<=b: print(i)

Buggy submission (verdict: Runtime Error):
a,b,k = map(int,input().split())
s = set(range(a,a+k))
t = set(range(b-k+1,b+1))
u = sorted(s|t)
for i in u: if a<=i<=b: print(i)
Problem p03387 (python)

Fixed submission:
def resolve():
    a,b,c=sorted(list(map(int,input().split())))
    ans=c-b
    a+=c-b
    b=c
    if (c-a)%2==0: print(ans+(c-a)//2)
    else: print(ans+2+(c-a)//2)
resolve()

Buggy submission (verdict: Runtime Error):
def resolve():
    a,b,c=sorted(list(map(int,input().split())))
    ans=c-b
    a+=c-b
    b=c
    if (c-a)%2==0: print(ans+(c-a)//2)
    else: print(ans+2+(c-a)//2)
resolve(
Problem p03391 (python)

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=[None]*n
    B=[None]*n
    for i in range(n):
        A[i],B[i]=map(int,input().split())

    if(A==B):
        print(0)
        return
    print(sum(A)-min(b for a,b in zip(A,B) if(a>b)))
resolve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=[None]*n
    B=[None]*n
    for i in range(n):
        A[i],B[i]=map(int,input().split())

    d=sum(b-a for a,b in zip(A,B) if(a<b))
    s=min(b for a,b in zip(A,B) if(a>=b and a-b<d))
    print(sum(A)-s)
resolve()
Problem p03409 (python)

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

from collections import deque
class Dinic:
    def __init__(self,n):
        self.__n=n
        self.__E=[[] for _ in range(n)]
        self.__depth=None
        self.__progress=None

    def add_link(self,u,v,w):
        self.__E[u].append([v,w,len(self.__E[v])])
        self.__E[v].append([u,0,len(self.__E[u])-1])

    def __bfs(self,s):
        depth=[-1]*self.__n
        depth[s]=0
        Q=deque([s])
        while(Q):
            v=Q.popleft()
            for nv,w,rev in self.__E[v]:
                if(w>0 and depth[nv]<0):
                    depth[nv]=depth[v]+1
                    Q.append(nv)
        self.__depth=depth

    def __dfs(self,v,t,flow):
        if(v==t): return flow
        for i in range(self.__progress[v],len(self.__E[v])):
            self.__progress[v]=i
            nv,w,rev=self.__E[v][i]
            if(w==0 or self.__depth[v]>=self.__depth[nv]): continue
            d=self.__dfs(nv,t,min(flow,w))
            if(d==0): continue
            self.__E[v][i][1]-=d
            self.__E[nv][rev][1]+=d
            return d
        return 0

    def flow(self,s,t):
        flow=0
        while(True):
            self.__bfs(s)
            if(self.__depth[t]<0): return flow
            self.__progress=[0]*self.__n
            current_flow=self.__dfs(s,t,INF)
            while(current_flow):
                flow+=current_flow
                current_flow=self.__dfs(s,t,INF)

def resolve():
    n=int(input())
    AB=[tuple(map(int,input().split())) for _ in range(n)]
    CD=[tuple(map(int,input().split())) for _ in range(n)]

    # bipartite の maximum matching で解く
    mf=Dinic(2*n+2)
    for i in range(n):
        mf.add_link(0,i+1,1)
        mf.add_link(n+i+1,2*n+1,1)
    for i in range(n):
        a,b=AB[i]
        for j in range(n):
            c,d=CD[j]
            if(a<c and b<d):
                mf.add_link(i+1,n+j+1,1)

    print(mf.flow(0,2*n+1))
resolve()

Buggy submission (verdict: Runtime Error):
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import maximum_bipartite_matching
def resolve():
    n = int(input())
    A = [tuple(map(int, input().split())) for _ in range(n)]
    B = [tuple(map(int, input().split())) for _ in range(n)]

    graph = csr_matrix([[int(A[i][0] < B[j][0] and A[i][1] < B[j][1]) for j in range(n)] for i in range(n)])
    ans = 0
    for a in maximum_bipartite_matching(graph):
        if a != -1:
            ans += 1
    print(ans)
resolve()
Problem p03421 (python)

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,a,b=map(int,input().split())
    if(a+b>n+1):
        print(-1)
        return
    if(a*b<n):
        print(-1)
        return

    ans=list(range(b,0,-1))
    now=b
    d=a*b-n
    for _ in range(a-1):
        k=min(d,b-1)
        d-=k
        next=now+(b-k)
        for i in range(next,now,-1):
            ans.append(i)
        now=next

    print(*ans)
resolve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,a,b=map(int,input().split())

    if(a+b>n+1):
        print(-1)
        return
    if(a*b<n):
        print(-1)
        return

    # a*b=n のとき
    A=[None]*(a*b)
    for i in range(a):
        for j in range(b):
            A[i*b+j]=(i+1)*b-j

    d=a*b-n
    m=0
    for i in range(1,a):
        k=min(b-1,d)
        d-=k
        m+=k
        for j in range(i*b,(i+1)*b):
            if(j>=(i+1)*b-k): A[j]=None
            else: A[j]-=m

    ans=[a for a in A if(a is not None)]
    print(*ans)
resolve()
Problem p03619 (python)

Fixed submission:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from math import pi
from bisect import bisect_left
def resolve():
    x1,y1,x2,y2=map(int,input().split())
    if(x1>x2): x1,y1,x2,y2=x2,y2,x1,y1 # x1<=x2
    trans=False
    if(y1>y2):
        y1,y2=-y1,-y2 # y1<=y2
        trans=True

    n=int(input())
    XY=[]
    for i in range(n):
        x,y=map(int,input().split())
        if(trans): y=-y
        if(x1<=x<=x2 and y1<=y<=y2):
            XY.append((x,y))

    d=(x2-x1)+(y2-y1) # マンハッタン
    d*=100
    l=min(x2-x1,y2-y1)

    # XYのLISを求めて、その個数*(20-5pi)を引けばよい
    XY.sort()
    C=[INF]*(n+1)
    for x,y in XY:
        i=bisect_left(C,y)
        C[i]=y
    k=C.index(INF)
    # LISの数が l より大きい時 -> 1回は無駄にしてしまう
    if(k>l):
        d-=(k-1)*(20-5*pi)
        d+=10*pi-20
    else:
        d-=k*(20-5*pi)
    print(d)
resolve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from math import pi
from bisect import bisect_left
def resolve():
    x1,y1,x2,y2=map(int,input().split())
    if(x1>x2): x1,y1,x2,y2=x2,y2,x1,y1 # x1<=x2
    trans=False
    if(y1>y2):
        y1,y2=10**8-y1,10**8-y2 # y1<=y2
        trans=True

    n=int(input())
    XY=[]
    for i in range(n):
        x,y=map(int,input().split())
        if(trans): y=10**8-y
        if(x1<=x<=x2 and y1<=y<=y2):
            XY.append((x,y))

    d=(x2-x1)+(y2-y1) # マンハッタン
    d*=100

    if(x1==x2 or y1==y2):
        assert(False)
        if(XY): d+=10*pi-20
        print(d)
        return

    # XYのLISを求めて、その個数*(20-5pi)を引けばよい
    XY.sort()
    C=[INF]*(n+1)
    for x,y in XY:
        i=bisect_left(C,y)
        C[i]=y
    k=C.index(INF)
    d-=k*(20-5*pi)
    print(d)
resolve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from math import pi
from bisect import bisect_left
def resolve():
    x1,y1,x2,y2=map(int,input().split())
    if(x1>x2): x1,y1,x2,y2=x2,y2,x1,y1 # x1<=x2
    trans=False
    if(y1>y2):
        y1,y2=10**8-y1,10**8-y2 # y1<=y2
        trans=True

    n=int(input())
    XY=[]
    for i in range(n):
        x,y=map(int,input().split())
        if(trans): x,y=10**8-x,10**8-y
        if(x1<=x<=x2 and y1<=y<=y2):
            XY.append((x,y))

    d=(x2-x1)+(y2-y1) # マンハッタン
    d*=100

    if(x1==x2 or y1==y2):
        if(XY): d+=10*pi-20
        print(d)
        return

    # XYのLISを求めて、その個数*(20-5pi)を引けばよい
    XY.sort()
    C=[INF]*n
    for x,y in XY:
        i=bisect_left(C,y)
        C[i]=y
    k=C.index(INF)
    d-=k*(20-5*pi)
    print(d)
resolve()