結果
問題 | No.2422 regisys? |
ユーザー |
|
提出日時 | 2024-03-06 08:00:11 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 272 ms / 2,000 ms |
コード長 | 1,673 bytes |
コンパイル時間 | 1,930 ms |
コンパイル使用メモリ | 197,456 KB |
実行使用メモリ | 16,944 KB |
最終ジャッジ日時 | 2024-09-29 18:14:08 |
合計ジャッジ時間 | 8,450 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 61 |
ソースコード
import std;void main () {int N, M; readln.read(N, M);auto A = readln.split.to!(int[]);auto B = readln.split.to!(int[]);int[] mma, non_mma;foreach (i; 0..M) {int T, C; readln.read(T, C);if (T == 0) non_mma ~= C;if (T == 1) mma ~= C;}solve(N, M, A, B, mma, non_mma);}void solve (int N, int M, int[] A, int[] B, int[] mma, int[] non_mma) {auto items = new Tuple!(int, int, int)[](N);foreach (i; 0..N) {items[i] = tuple(i, A[i], B[i]);}items.sort!"a[1] < b[1]";non_mma.sort;auto used = new bool[](N);{BinaryHeap!(Tuple!(int, int)[], "a[1] < b[1]") PQ = [];// rangeだけ使うauto r = items;foreach (v; non_mma) {while (!r.empty && r.front[1] <= v) {PQ.insert(tuple(r.front[0], r.front[2]));r.popFront;}if (PQ.empty) continue;used[PQ.front[0]] = true;PQ.removeFront;}}mma.sort;BinaryHeap!(Tuple!(int, int)[], "b[1] < a[1]") PQ = [];foreach (i; 0..N) {if (used[items[i][0]]) continue;PQ.insert(tuple(items[i][0], items[i][2]));}foreach (v; mma) {if (PQ.empty) break;if (v < PQ.front[1]) continue;used[PQ.front[0]] = true;PQ.removeFront;}int ans = 0;foreach (i; 0..N) if (!used[i]) ans++;writeln(ans);}void read (T...) (string S, ref T args) {import std.conv : to;import std.array : split;auto buf = S.split;foreach (i, ref arg; args) {arg = buf[i].to!(typeof(arg));}}