Table of Contents

ExplanationImplementation

Explanation

We need to be able to quickly add elements to a set of numbers, as well as access and remove the smallest and largest ones.

For C++, we use a std::multiset to ensure a sorted order.

For Java, we use a TreeMap for the same reason.

For Python, we use a min_heap, max_heap, and a counts dictionary. The min_heap and max_heap are for access, while the counts dictionary determines removal.

Implementation

Time Complexity: O((N+Q)log⁡N)\mathcal{O}((N+Q)\log N)

C++

#include <iostream>
#include <set>
using namespace std;


int main() {
	int n, q;
	cin >> n >> q;


	multiset<int> st;
	for (int i = 0; i < n; i++) {

Java

import java.io.*;
import java.util.*;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());


		int n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());

Python

import heapq


n, q = map(int, input().split())
nums = list(map(int, input().split()))


min_heap = []
max_heap = []
count = {}
for num in nums:
	heapq.heappush(min_heap, num)

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum