Table of Contents

ExplanationImplementation

Official Analysis (Java)

Explanation

We keep three prefix sum arrays: one for Holsteins, one for Guernseys, and one for Jerseys. These arrays allow us to calculate how many cows of each breed exist on an interval.

To find the amount of Holsteins/Guernseys/Jerseys on an interval [l,r][l, r], we use

p[r]−p[l−1],p[r] - p[l-1],

where pp is the respective prefix array.

Implementation

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

C++

#include <iostream>
#include <vector>


using namespace std;


int main() {
	freopen("bcount.in", "r", stdin);
	freopen("bcount.out", "w", stdout);


	int cow_num;

Java

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


public class BCount {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("bcount.in"));
		PrintWriter out =
		    new PrintWriter(new BufferedWriter(new FileWriter("bcount.out")));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int cowNum = Integer.parseInt(initial.nextToken());

Python

with open("bcount.in") as read:
	cow_num, query_num = [int(i) for i in read.readline().split()]
	holsteins = [0]
	guernseys = [0]
	jerseys = [0]
	for _ in range(cow_num):
		holsteins.append(holsteins[-1])
		guernseys.append(guernseys[-1])
		jerseys.append(jerseys[-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