Table of Contents

ExplanationImplementation

Official Editorial (C++/Java)

Explanation

We can calculate the contribution of each index in the range query using a difference array technique.

To maximize the sum, sort both the array and frequency array in ascending order and pair the elements of the array with their respective frequencies, ignoring the first element of frequency array.

Implementation

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

C++

#include <algorithm>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


int main() {
	int n, q;

Java

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


public class LittleGirlMaxSum {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int q = io.nextInt();


		int[] arr = new int[n];

Python

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


freq = [0] * (n + 1)
for _ in range(q):
	l, r = map(int, input().split())
	freq[l - 1] += 1
	freq[r] -= 1


for i in range(1, n + 1):

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