Submission #1543551


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
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)])
    dx = {}
    dy = {}
    t = sorted([x1,x2] + list(map(lambda x: x[0], a)))
    dx[t[0]] = c = 1
    for i in range(1,n+2):
        if t[i-1] == t[i]:
            continue
        c += 1
        dx[t[i]] = c
    t = sorted([y1,y2] + list(map(lambda x: x[1], a)))
    dy[t[0]] = c = 1
    for i in range(1,n+2):
        if t[i-1] == t[i]:
            continue
        c += 1
        dy[t[i]] = c

    r = (abs(x2-x1) + abs(y2-y1)) * 100
    x1 = dx[x1]
    x2 = dx[x2]
    y1 = dy[y1]
    y2 = dy[y2]
    a = list(map(lambda x: [dx[x[0]], dy[x[1]]], a))

    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+10,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)

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

Submission Info

Submission Time
Task C - Fountain Walk
User iehn
Language PyPy3 (2.4.0)
Score 0
Code Size 2949 Byte
Status WA
Exec Time 2110 ms
Memory 131760 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 3
AC × 31
WA × 10
TLE × 6
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 401 ms 67180 KB
sample_02.txt AC 269 ms 64236 KB
sample_03.txt AC 272 ms 64236 KB
subtask_1_01.txt AC 269 ms 64236 KB
subtask_1_02.txt WA 271 ms 64236 KB
subtask_1_03.txt WA 268 ms 64236 KB
subtask_1_04.txt WA 271 ms 64236 KB
subtask_1_05.txt AC 269 ms 64364 KB
subtask_1_06.txt AC 269 ms 64236 KB
subtask_1_07.txt AC 275 ms 64236 KB
subtask_1_08.txt AC 274 ms 64236 KB
subtask_1_09.txt AC 626 ms 102232 KB
subtask_1_10.txt AC 1061 ms 128596 KB
subtask_1_11.txt AC 459 ms 87640 KB
subtask_1_12.txt TLE 2110 ms 130400 KB
subtask_1_13.txt AC 1111 ms 119300 KB
subtask_1_14.txt AC 626 ms 101592 KB
subtask_1_15.txt AC 451 ms 86104 KB
subtask_1_16.txt TLE 2110 ms 130400 KB
subtask_1_17.txt WA 942 ms 128880 KB
subtask_1_18.txt WA 780 ms 119380 KB
subtask_1_19.txt WA 811 ms 119256 KB
subtask_1_20.txt TLE 2109 ms 129280 KB
subtask_1_21.txt TLE 2110 ms 130400 KB
subtask_1_22.txt TLE 2110 ms 130400 KB
subtask_1_23.txt AC 1992 ms 130528 KB
subtask_1_24.txt WA 276 ms 64488 KB
subtask_1_25.txt WA 267 ms 64236 KB
subtask_1_26.txt WA 266 ms 64236 KB
subtask_1_27.txt WA 267 ms 64236 KB
subtask_1_28.txt AC 1373 ms 130144 KB
subtask_1_29.txt AC 1456 ms 129904 KB
subtask_1_30.txt TLE 2110 ms 131760 KB
subtask_1_31.txt AC 1473 ms 127840 KB
subtask_1_32.txt AC 1606 ms 127968 KB
subtask_1_33.txt AC 1507 ms 127840 KB
subtask_1_34.txt AC 1507 ms 127968 KB
subtask_1_35.txt AC 1605 ms 129504 KB
subtask_1_36.txt AC 1514 ms 130272 KB
subtask_1_37.txt AC 1607 ms 128352 KB
subtask_1_38.txt AC 1396 ms 128736 KB
subtask_1_39.txt AC 1799 ms 128480 KB
subtask_1_40.txt AC 1413 ms 128736 KB
subtask_1_41.txt AC 1592 ms 128736 KB