結果
問題 | No.1703 Much Matching |
ユーザー |
👑 |
提出日時 | 2022-01-01 21:00:53 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 864 ms / 2,000 ms |
コード長 | 1,237 bytes |
コンパイル時間 | 56 ms |
コンパイル使用メモリ | 6,692 KB |
実行使用メモリ | 11,648 KB |
最終ジャッジ日時 | 2024-10-10 14:11:33 |
合計ジャッジ時間 | 6,826 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
local mmi, mma = math.min, math.maxlocal mfl = math.floorlocal function comp(a, b)return a < bendlocal function lower_bound(ary, x)local num = #aryif num == 0 then return 1 endif not comp(ary[1], x) then return 1 endif comp(ary[num], x) then return num + 1 endlocal min, max = 1, numwhile 1 < max - min dolocal mid = mfl((min + max) / 2)if comp(ary[mid], x) thenmin = midelsemax = midendendreturn maxendlocal n, m, q = io.read("*n", "*n", "*n")local dp1, dp2 = {}, {}local t = {}for i = 1, n dot[i] = {}endfor i = 1, q dolocal a, b = io.read("*n", "*n")table.insert(t[a], b)endfor i = 1, n dotable.sort(t[i])endfor i = 1, n dolocal src = i % 2 == 1 and dp1 or dp2local dst = i % 2 == 1 and dp2 or dp1for j = 1, i - 1 dodst[j] = src[j]enddst[i] = m + 1for j = i - 1, 1, -1 doif src[j] <= m thenlocal lb = lower_bound(t[i], src[j] + 1)if lb <= #t[i] thendst[j + 1] = mmi(dst[j + 1], t[i][lb])endendendif 0 < #t[i] thendst[1] = mmi(dst[1], t[i][1])endendlocal tbl = n % 2 == 1 and dp2 or dp1for i = n, 1, -1 doif tbl[i] <= m then print(i) os.exit() endendprint(0)