Problem p03619 (python)

Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func

    def find(self, i):
        return self.A[i + self.N]

    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 1:
            i = i // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[1]

    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1

        return res

def main():
    txy = LI()
    x1,y1,x2,y2 = txy
    n = I()
    a = [LI() for _ in range(n)]
    im = 10**8
    xs = set([x1,x2])
    ys = set([y1,y2])
    for x,y in a:
        xs.add(x)
        ys.add(y)
    xd = {}
    yd = {}
    i = 0
    for x in sorted(list(xs)):
        xd[x] = i
        i += 1
    i = 0
    for y in sorted(list(ys)):
        yd[y] = i
        i += 1
    x1 = xd[x1]
    x2 = xd[x2]
    y1 = yd[y1]
    y2 = yd[y2]
    a = [[xd[x],yd[y]] for x,y in a]

    if x1 > x2:
        x2,y2,x1,y1 = x1,y1,x2,y2
    if y1 > y2:
        y1 = im - y1
        y2 = im - y2 - y1
        for i in range(n):
            a[i][1] = im - a[i][1] - y1
    else:
        y2 -= y1
        for i in range(n):
            a[i][1] -= y1
    y1 = 0

    x2 -= x1
    for i in range(n):
        a[i][0] -= x1
    x1 = 0

    def f(a,b):
        if a > b:
            return a
        return b

    seg = Seg(y2,0,f)

    for x,y in sorted(a):
        if x < 0 or y < 0 or y > y2 or x > x2:
            continue
        t = seg.query(0,y)
        if seg.find(y) > t:
            continue
        seg.update(y, t+1)

    t = seg.total()
    kx = abs(txy[0]-txy[2])
    ky = abs(txy[1]-txy[3])
    r = (kx+ky) * 100
    if t == min(kx, ky) + 1:
        return r - t * 20 + math.pi * 5 * (t-1)  + math.pi * 10

    return r - t * 20 + math.pi * 5 * t


print(main())

Buggy submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

class Seg():
    def __init__(self, n, default, func):
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        self.A = [default] * (self.N*2-1)
        self.F = func

    def find(self, i):
        return self.A[i + self.N - 1]

    def update(self, i, x):
        i += self.N - 1
        self.A[i] = x
        while i > 0:
            i = (i-1) // 2
            self.A[i] = self.merge(self.A[i*2+1], self.A[i*2+2])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[0]

    def query(self, a, b):
        def _query(k,l,r):
            if r <= a or b <= l:
                return self.D
            if a <= l and r <= b:
                return self.A[k]
            m = (l+r)//2
            vl = _query(k*2+1,l,m)
            vr = _query(k*2+2,m,r)
            return self.merge(vl,vr)
        return _query(0,0,self.N)


def main():
    x1,y1,x2,y2 = LI()
    n = I()
    a = sorted([LI() for _ in range(n)])
    if x1 > x2:
        x1,y1,x2,y2 = x2,y2,x1,y1
    yy1 = y1
    yy2 = y2
    if yy1 > yy2:
        yy1,yy2 = yy2,yy1

    def f(a,b):
        if a>b:
            return a
        return b

    s = Seg(n+2,0,f)

    yf = y2 < y1
    for x,y in a:
        if x < x1:
            continue
        if x > x2:
            continue
        if y < yy1:
            continue
        if y > yy2:
            continue
        if yf:
            y = n-y+1
        t = s.query(0,y)
        s.update(y,t+1)

    r = (abs(x2-x1) + abs(y2-y1)) * 100
    y = y2
    if yf:
        y = n-y2+1
    k = 20 - 5 * math.pi
    t = s.total()
    r = r-t*k
    if t > min(abs(x2-x1),abs(y1-y2)):
        r += 5 * math.pi

    return r

print(main())

Buggy submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

class Seg():
    def __init__(self, n, default, func):
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        self.A = [default] * (self.N*2-1)
        self.F = func

    def find(self, i):
        return self.A[i + self.N - 1]

    def update(self, i, x):
        i += self.N - 1
        self.A[i] = x
        while i > 0:
            i = (i-1) // 2
            self.A[i] = self.merge(self.A[i*2+1], self.A[i*2+2])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[0]

    def query(self, a, b):
        def _query(k,l,r):
            if r <= a or b <= l:
                return self.D
            if a <= l and r <= b:
                return self.A[k]
            m = (l+r)//2
            vl = _query(k*2+1,l,m)
            vr = _query(k*2+2,m,r)
            return self.merge(vl,vr)
        return _query(0,0,self.N)


def main():
    x1,y1,x2,y2 = LI()
    n = I()
    a = sorted([LI() for _ in range(n)])
    if x1 > x2:
        x1,y1,x2,y2 = x2,y2,x1,y1
    yy1 = y1
    yy2 = y2
    if yy1 > yy2:
        yy1,yy2 = yy2,yy1

    def f(a,b):
        if a>b:
            return a
        return b

    s = Seg(n+2,0,f)

    yf = y2 < y1
    for x,y in a:
        if x < x1:
            continue
        if x > x2:
            continue
        if y < yy1:
            continue
        if y > yy2:
            continue
        if yf:
            y = n-y+1
        t = s.query(0,y)
        s.update(y,t+1)

    r = (abs(x2-x1) + abs(y2-y1)) * 100
    y = y2
    if yf:
        y = n-y2+1
    k = 20 - 5 * math.pi
    t = s.total()
    r = r-t*k
    if t > min(abs(x2-x1),abs(y1-y2)):
        r += 5 * math.pi

    return r

print(main())