Submission #74943549

Source Code Expand

import sys
from sortedcontainers import SortedList

def solve():
    data = sys.stdin.read().split()
    idx = 0
    n, m = int(data[idx]), int(data[idx+1])
    idx += 2

    plans = [int(data[idx+i]) for i in range(n)]
    idx += n

    barricades = SortedList()
    for i in range(m):
        barricades.add(int(data[idx+i]))

    lo, hi = 0, 0  # reachable range [lo, hi]

    for d in plans:
        if d > 0:
            # Moving right: sweep region is [lo, hi+d]
            # Blocked if any barricade in (lo, hi+d] ... 
            # Actually: from any s in [lo,hi], move covers [s, s+d]
            # Barricade blocks if X in [s, s+d] for some s in [lo,hi]
            # = barricade in [lo, hi+d]
            check_lo = lo
            check_hi = hi + d
        else:
            # Moving left: from s covers [s+d, s]
            # = barricade in [lo+d, hi]
            check_lo = lo + d
            check_hi = hi

        # Check if any barricade exists in [check_lo, check_hi]
        pos = barricades.bisect_left(check_lo)
        blocked = (pos < len(barricades) and barricades[pos] <= check_hi)

        if not blocked:
            # Can choose to execute or skip → expand range
            lo = min(lo, lo + d)
            hi = max(hi, hi + d)
        # else: must skip, range unchanged

    print(hi)

solve()

Submission Info

Submission Time
Task E - A Walk and Barricades
User mutharasim
Language Python (PyPy 3.11-v7.3.20)
Score 0
Code Size 1370 Byte
Status WA
Exec Time 282 ms
Memory 152680 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 466
Status
AC × 5
AC × 40
WA × 12
Set Name Test Cases
Sample sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt
All sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in46.txt, in47.txt
Case Name Status Exec Time Memory
in01.txt AC 141 ms 114092 KiB
in02.txt AC 144 ms 114008 KiB
in03.txt AC 141 ms 114120 KiB
in04.txt AC 141 ms 113844 KiB
in05.txt AC 143 ms 113960 KiB
in06.txt WA 140 ms 113852 KiB
in07.txt WA 141 ms 113628 KiB
in08.txt AC 140 ms 113784 KiB
in09.txt WA 142 ms 113952 KiB
in10.txt WA 141 ms 113844 KiB
in11.txt AC 140 ms 113952 KiB
in12.txt AC 140 ms 114280 KiB
in13.txt AC 139 ms 113668 KiB
in14.txt AC 139 ms 113848 KiB
in15.txt AC 141 ms 113948 KiB
in16.txt AC 140 ms 113832 KiB
in17.txt WA 139 ms 113996 KiB
in18.txt WA 141 ms 113604 KiB
in19.txt AC 140 ms 114112 KiB
in20.txt AC 142 ms 113956 KiB
in21.txt WA 143 ms 114140 KiB
in22.txt WA 144 ms 113876 KiB
in23.txt WA 139 ms 114072 KiB
in24.txt WA 138 ms 114000 KiB
in25.txt WA 139 ms 114220 KiB
in26.txt WA 138 ms 113972 KiB
in27.txt AC 140 ms 114088 KiB
in28.txt AC 140 ms 113884 KiB
in29.txt AC 142 ms 113972 KiB
in30.txt AC 142 ms 114120 KiB
in31.txt AC 161 ms 120304 KiB
in32.txt AC 168 ms 120820 KiB
in33.txt AC 262 ms 142104 KiB
in34.txt AC 264 ms 142208 KiB
in35.txt AC 166 ms 120952 KiB
in36.txt AC 165 ms 120952 KiB
in37.txt AC 144 ms 117404 KiB
in38.txt AC 233 ms 151092 KiB
in39.txt AC 229 ms 147832 KiB
in40.txt AC 232 ms 147744 KiB
in41.txt AC 235 ms 148308 KiB
in42.txt AC 233 ms 145012 KiB
in43.txt AC 279 ms 152680 KiB
in44.txt AC 282 ms 152108 KiB
in45.txt AC 147 ms 117364 KiB
in46.txt AC 246 ms 152284 KiB
in47.txt AC 242 ms 147948 KiB
sample01.txt AC 139 ms 113960 KiB
sample02.txt AC 139 ms 114192 KiB
sample03.txt AC 139 ms 113896 KiB
sample04.txt AC 139 ms 114216 KiB
sample05.txt AC 139 ms 113836 KiB