Set<T> (Library Checker: Double-Ended Priority Queue) (CpLibrary.Verify/Collections/DoubleEndedPriorityQueue.cs)

• View this file on GitHub
• Last update: 2025-01-29 12:37:39+09:00
• Problem: https://judge.yosupo.jp/problem/double_ended_priority_queue

Depends on

• CpLibrary/Collections/MultiSet.cs
• CpLibrary/Collections/Set.cs
• CpLibrary/IO/Scanner.cs

Code

using CpLibrary.Collections;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CpLibrary.Verify.Collections
{
	// competitive-verifier: document_title Set<T> (Library Checker: Double-Ended Priority Queue)
	internal class DoubleEndedPriorityQueue : CompetitiveVerifier.ProblemSolver
	{
		public override string Url => "https://judge.yosupo.jp/problem/double_ended_priority_queue";
		public override void Solve()
		{
			var sr = new Scanner(new StreamReader(Console.OpenStandardInput()));

			var (n, q) = sr.ReadValue<int, int>();
			var s = sr.ReadLongArray(n);
			var set = new MultiSet<long>(s);
			for (int i = 0; i < q; i++)
			{
				var query = sr.ReadInt();
				if (query == 0)
				{
					var x = sr.ReadInt();
					set.Add(x);
				}
				else if (query == 1)
				{
					Console.WriteLine(set.Min());
					set.RemoveAt(0);
				}
				else
				{
					Console.WriteLine(set.Max());
					set.RemoveAt(set.Count - 1);
				}
			}
		}
	}
}

Test cases

Env	Name	Status	Elapsed	Memory
	example_00	AC	55 ms	29 MB
	random_n_max_q_max_00	AC	1694 ms	121 MB
	random_n_max_q_max_01	AC	1771 ms	121 MB
	random_n_max_q_max_many_pop_00	AC	1686 ms	120 MB
	random_n_max_q_max_many_pop_01	AC	1731 ms	120 MB
	random_n_max_q_max_only_type01_00	AC	1644 ms	120 MB
	random_n_max_q_max_only_type01_01	AC	1703 ms	120 MB
	random_n_max_q_max_small_value_00	AC	1470 ms	111 MB
	random_n_max_q_max_small_value_01	AC	1544 ms	110 MB
	random_n_zero_q_max_00	AC	687 ms	47 MB
	random_small_00	AC	56 ms	29 MB
	random_small_01	AC	56 ms	29 MB
	random_small_02	AC	55 ms	29 MB
	random_small_03	AC	51 ms	29 MB
	random_small_only_type01_00	AC	61 ms	29 MB
	random_small_only_type01_01	AC	63 ms	29 MB
	random_small_only_type01_02	AC	64 ms	29 MB
	random_small_only_type01_03	AC	58 ms	29 MB

Back to top page