Submission #1181897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181897		mehmetkagan	Arcade (NOI20_arcade)	Pypy 3	0 / 100	136 ms	48792 KiB

Arcade

import sys
import bisect

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    # Parse input
    N = int(data[0])
    M = int(data[1])
    T = list(map(int, data[2:2+M]))
    A = list(map(int, data[2+M:2+2*M]))
    
    # Build events: each event becomes (L, R)
    events = []
    for i in range(M):
        L = T[i] - A[i]
        R = T[i] + A[i]
        events.append((L, R))
    
    # Sort events by L ascending; if L is equal, sort by R descending.
    events.sort(key=lambda x: (x[0], -x[1]))
    
    # We now wish to compute the length of the longest strictly decreasing subsequence in R.
    # Equivalently, compute the longest strictly increasing subsequence in x = -R.
    lis = []
    for L, R in events:
        x = -R
        pos = bisect.bisect_left(lis, x)
        if pos == len(lis):
            lis.append(x)
        else:
            lis[pos] = x
    # The length of lis is the minimum number of hands S.
    print(len(lis))

if __name__ == "__main__":
    main()

Compilation message (stdout)

Compiling 'Arcade.py'...

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

=======

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 14
• Subtask 6: 0 / 20
• Subtask 7: 0 / 15