USACO 2015 December Contest Silver Division - Breed Counting

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This is a classical prefix sum exercise, where our goal is to compute fast how many cows of a certain breed exist on a segment in the array. In order to do that, we will construct prefix sums for each of the three breeds and print these answers one by one.

Source code

The source code in C++ can be seen below.

#include <fstream>
#include <vector>
using namespace std;

int main() {
    ifstream cin("bcount.in");
    ofstream cout("bcount.out");

    int n, q;
    cin >> n >> q;

    vector<int> v(n + 1);
    vector<vector<int> > ps(4, vector<int>(n + 1));

    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        for (int j = 1; j <= 3; j++) {
            ps[j][i] = ps[j][i - 1] + (v[i] == j);
        }
    }

    while (q--) {
        int L, R;
        cin >> L >> R;
        int ones = ps[1][R] - ps[1][L - 1];
        int twos = ps[2][R] - ps[2][L - 1];
        int threes = ps[3][R] - ps[3][L - 1];
        cout << ones << " " << twos << " " << threes << '\n';
    }

    return 0;
}