結果
問題 | No.1508 Avoid being hit |
ユーザー |
![]() |
提出日時 | 2021-05-14 23:00:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 184 ms / 3,000 ms |
コード長 | 1,609 bytes |
コンパイル時間 | 376 ms |
コンパイル使用メモリ | 82,464 KB |
実行使用メモリ | 102,016 KB |
最終ジャッジ日時 | 2024-10-02 07:08:50 |
合計ジャッジ時間 | 6,841 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
import sys readline = sys.stdin.readline N, Q = map(int, readline().split()) ok = [None]*(Q+1) ok[-1] = [(1, N+1)] A = list(map(int, readline().split())) B = list(map(int, readline().split())) INF = 10**9+7 for i in range(Q): a, b = A[i], B[i] res = [] for l, r in ok[i-1]: res.append((max(1, l-1), min(N+1, r+1))) st = -INF en = -INF res2 = [] for l, r in res: if en < l: if st != en: res2.append((st, en)) st = l en = r if st != en: res2.append((st, en)) res3 = [] for l, r in res2: if l <= a < r: if l != a: res3.append((l, a)) if r-1 != a: res3.append((a+1, r)) else: res3.append((l, r)) res4 = [] for l, r in res3: if l <= b < r: if l != b: res4.append((l, b)) if r-1 != b: res4.append((b+1, r)) else: res4.append((l, r)) ok[i] = res4[:] if not ok[Q-1]: print("NO") else: print("YES") ans = [ok[Q-1][0][0]] for i in range(Q-2, -2, -1): for l, r in ok[i]: if l <= ans[-1]-1 < r: ans.append(ans[-1]-1) break if l <= ans[-1] < r: ans.append(ans[-1]) break if l <= ans[-1]+1 < r: ans.append(ans[-1]+1) break else: assert False print('\n'.join(map(str, ans[::-1])))