結果
問題 | No.2422 regisys? |
ユーザー |
|
提出日時 | 2023-10-09 13:28:49 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 580 ms / 2,000 ms |
コード長 | 3,688 bytes |
コンパイル時間 | 1,301 ms |
コンパイル使用メモリ | 116,164 KB |
実行使用メモリ | 64,216 KB |
最終ジャッジ日時 | 2024-07-26 18:31:42 |
合計ジャッジ時間 | 14,887 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 61 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using static System.Console;using System.Linq;using System.Collections.Generic;class Program{static int NN => int.Parse(ReadLine());static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();public static void Main(){Solve();}static void Solve(){var c = NList;var (n, m) = (c[0], c[1]);var a = NList;var b = NList;var map = NArr(m);var list = new List<(int id, int b)>(n);for (var i = 0; i < n; ++i) list.Add((i, b[i]));list.Sort((l, r) => r.b.CompareTo(l.b));var mmas = new List<int>();var ppls = new List<int>();for (var i = 0; i < m; ++i){if (map[i][0] == 0) ppls.Add(map[i][1]);else mmas.Add(map[i][1]);}mmas.Sort();ppls.Sort();var q = new PriorityQueue<int>(n, true);var ans = n;for (var i = 0; i < mmas.Count; ++i){while (list.Count > 0 && list[list.Count - 1].b <= mmas[i]){q.Enqueue(a[list[list.Count - 1].id]);list.RemoveAt(list.Count - 1);}if (q.Count > 0){q.Dequeue();--ans;}}var rest = new List<int>(list.Select(li => a[li.id]));while (q.Count > 0) rest.Add(q.Dequeue());rest.Sort((l, r) => r.CompareTo(l));for (var i = 0; i < ppls.Count; ++i){if (rest.Count > 0 && rest[rest.Count - 1] <= ppls[i]){--ans;rest.RemoveAt(rest.Count - 1);}}WriteLine(ans);}class PriorityQueue<T> where T : IComparable<T>{public T[] List;public int Count;bool IsTopMax;public PriorityQueue(int count, bool isTopMax){IsTopMax = isTopMax;List = new T[Math.Max(128, count)];}public void Enqueue(T value){if (Count == List.Length){var newlist = new T[List.Length * 2];for (var i = 0; i < List.Length; ++i) newlist[i] = List[i];List = newlist;}var pos = Count;List[pos] = value;++Count;while (pos > 0){var parent = (pos - 1) / 2;if (Calc(List[parent], List[pos], true)) break;Swap(parent, pos);pos = parent;}}public T Dequeue(){--Count;Swap(0, Count);var pos = 0;while (true){var child = pos * 2 + 1;if (child >= Count) break;if (child + 1 < Count && Calc(List[child + 1], List[child], false)) ++child;if (Calc(List[pos], List[child], true)) break;Swap(pos, child);pos = child;}return List[Count];}bool Calc(T a, T b, bool equalVal){var ret = a.CompareTo(b);if (ret == 0 && equalVal) return true;return IsTopMax ? ret > 0 : ret < 0;}void Swap(int a, int b){var tmp = List[a];List[a] = List[b];List[b] = tmp;}}}