Submission #1187919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187919		ofoz	Infinite Race (EGOI24_infiniterace2)	Pypy 3	100 / 100	245 ms	82584 KiB

Main

from sys import setrecursionlimit, stdout
from math import ceil, floor



def solve():
    n = int(input())
    q = int(input())
    lapped = dict()
    for i in range(n): lapped[i] = 0

    currentAhead = set()
    res = 0
    for _ in range(q):
        x = int(input())
        i = abs(x)
        if x < 0:
            if i in currentAhead: currentAhead.remove(i)
        elif i in currentAhead:
            res += 1
            currentAhead.clear()
            currentAhead.add(i)
        else:
            currentAhead.add(i)

    # print(lapped)
    print(res)

    return

# for us to be sure that she must have crossed the finish line,
# she must overtake someone that she just overtook. and since, its the minimal case, the answer will be the maximum of all the times she overtook someone she just overtook
# let a[i] be 0 if theyre ahead of her and 1 if behind her. 

# 
solve()

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 31%)

=======

• Subtask 1: 29 / 29
• Subtask 2: 34 / 34
• Subtask 3: 22 / 22
• Subtask 4: 15 / 15