Submission #2203253


Source Code Expand

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())


Submission Info

Submission Time
Task C - Fountain Walk
User iehn
Language PyPy3 (2.4.0)
Score 900
Code Size 3365 Byte
Status AC
Exec Time 1829 ms
Memory 144732 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 47
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt
Case Name Status Exec Time Memory
sample_01.txt AC 294 ms 64236 KB
sample_02.txt AC 298 ms 64236 KB
sample_03.txt AC 304 ms 64236 KB
subtask_1_01.txt AC 303 ms 64364 KB
subtask_1_02.txt AC 307 ms 64236 KB
subtask_1_03.txt AC 309 ms 64236 KB
subtask_1_04.txt AC 305 ms 64236 KB
subtask_1_05.txt AC 312 ms 64236 KB
subtask_1_06.txt AC 307 ms 64236 KB
subtask_1_07.txt AC 297 ms 64236 KB
subtask_1_08.txt AC 294 ms 64236 KB
subtask_1_09.txt AC 665 ms 101336 KB
subtask_1_10.txt AC 1113 ms 117976 KB
subtask_1_11.txt AC 497 ms 90712 KB
subtask_1_12.txt AC 1712 ms 142640 KB
subtask_1_13.txt AC 1199 ms 121100 KB
subtask_1_14.txt AC 679 ms 101848 KB
subtask_1_15.txt AC 479 ms 88184 KB
subtask_1_16.txt AC 1706 ms 142640 KB
subtask_1_17.txt AC 1042 ms 125132 KB
subtask_1_18.txt AC 835 ms 120780 KB
subtask_1_19.txt AC 949 ms 120524 KB
subtask_1_20.txt AC 1748 ms 142640 KB
subtask_1_21.txt AC 1738 ms 144732 KB
subtask_1_22.txt AC 1711 ms 142640 KB
subtask_1_23.txt AC 1714 ms 144164 KB
subtask_1_24.txt AC 301 ms 64236 KB
subtask_1_25.txt AC 296 ms 64236 KB
subtask_1_26.txt AC 299 ms 64236 KB
subtask_1_27.txt AC 305 ms 64236 KB
subtask_1_28.txt AC 1473 ms 142640 KB
subtask_1_29.txt AC 1577 ms 142640 KB
subtask_1_30.txt AC 1829 ms 142768 KB
subtask_1_31.txt AC 934 ms 142640 KB
subtask_1_32.txt AC 991 ms 142640 KB
subtask_1_33.txt AC 957 ms 142640 KB
subtask_1_34.txt AC 971 ms 142704 KB
subtask_1_35.txt AC 1115 ms 142640 KB
subtask_1_36.txt AC 1211 ms 142640 KB
subtask_1_37.txt AC 1137 ms 142640 KB
subtask_1_38.txt AC 1149 ms 142768 KB
subtask_1_39.txt AC 1130 ms 142640 KB
subtask_1_40.txt AC 1143 ms 142640 KB
subtask_1_41.txt AC 1121 ms 142640 KB