Submission #1542971


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

Submission Info

Submission Time
Task C - Fountain Walk
User iehn
Language PyPy3 (2.4.0)
Score 0
Code Size 2407 Byte
Status RE
Exec Time 1471 ms
Memory 124120 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 3
AC × 23
RE × 24
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 386 ms 67180 KB
sample_02.txt AC 281 ms 64236 KB
sample_03.txt AC 285 ms 64236 KB
subtask_1_01.txt AC 287 ms 64236 KB
subtask_1_02.txt AC 289 ms 64236 KB
subtask_1_03.txt AC 293 ms 64236 KB
subtask_1_04.txt AC 291 ms 64236 KB
subtask_1_05.txt AC 289 ms 64236 KB
subtask_1_06.txt AC 286 ms 64236 KB
subtask_1_07.txt AC 292 ms 64236 KB
subtask_1_08.txt AC 287 ms 64236 KB
subtask_1_09.txt RE 573 ms 80472 KB
subtask_1_10.txt RE 899 ms 95448 KB
subtask_1_11.txt RE 434 ms 73048 KB
subtask_1_12.txt RE 1151 ms 111320 KB
subtask_1_13.txt RE 964 ms 98392 KB
subtask_1_14.txt RE 580 ms 79960 KB
subtask_1_15.txt RE 422 ms 72152 KB
subtask_1_16.txt RE 1140 ms 106968 KB
subtask_1_17.txt RE 838 ms 90200 KB
subtask_1_18.txt RE 702 ms 85208 KB
subtask_1_19.txt RE 677 ms 84952 KB
subtask_1_20.txt RE 1129 ms 106628 KB
subtask_1_21.txt RE 1175 ms 109272 KB
subtask_1_22.txt RE 1156 ms 106840 KB
subtask_1_23.txt RE 1146 ms 106968 KB
subtask_1_24.txt AC 285 ms 64236 KB
subtask_1_25.txt AC 284 ms 64236 KB
subtask_1_26.txt AC 294 ms 64236 KB
subtask_1_27.txt AC 294 ms 64236 KB
subtask_1_28.txt AC 1263 ms 109912 KB
subtask_1_29.txt RE 1140 ms 106968 KB
subtask_1_30.txt RE 1132 ms 106968 KB
subtask_1_31.txt AC 1398 ms 114648 KB
subtask_1_32.txt AC 1420 ms 124120 KB
subtask_1_33.txt AC 1387 ms 123736 KB
subtask_1_34.txt AC 1471 ms 114932 KB
subtask_1_35.txt RE 564 ms 104664 KB
subtask_1_36.txt RE 577 ms 104664 KB
subtask_1_37.txt RE 570 ms 104792 KB
subtask_1_38.txt RE 575 ms 104664 KB
subtask_1_39.txt RE 560 ms 104664 KB
subtask_1_40.txt RE 579 ms 104664 KB
subtask_1_41.txt RE 559 ms 104664 KB