USACO Platinum 2017 February - Why Did the Cow Cross the Road III

External Solution

Solution 1

Easy with the offline 2D BIT mentioned in the module.

Time Complexity: $\mathcal{O}(N\log^2N)$

Memory Complexity: $\mathcal{O}(N\log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string;  // yay python!

using pi = pair<int, int>;
using pl = pair<ll, ll>;

Solution 2

Use a segment tree + BIT (online) as mentioned in the solution to Mowing the Field. You will run into time / memory limits unless you optimize appropriately ...

Time Complexity: $\mathcal{O}(N\log^2N)$

Memory Complexity: $\mathcal{O}(N\log^2 N)$

My solution (from a while ago):

Copy
#include <fstream>
#include <iostream>

using namespace std;

typedef pair<int, int> pi;

#define FOR(i, a, b) for (int i = a; i < b; i++)
#define F0R(i, a) for (int i = 0; i < a; i++)

Solution 3

After generating the appropriate sequence of updates and queries, can apply divide & conquer as described in the module.

Solution 4

Let us consider an easier version; suppose that we just want to count the number of crossing pairs (ignoring whether the cows are friendly or not). To calculate the number of crossing pairs, we can add the cows in road 1 in reverse, while counting the number of cows that are added before in road 2. We can use a binary indexed tree to count this. This takes $\mathcal O(N)$ space and $\mathcal O(N\log N)$ time.

To count the number of unfriendly crossings, instead of keeping track of the count for each BIT node, we maintain a sorted set representing the cow breeds. For a breed $b$, we query the number of breeds in the range $[1, b-k-1]$ and $[b+k+1, n]$. We can use a Order Statistic Tree in C++ to represent the cow breeds. Since each update takes $\log N$ operations, it would allocate $\log N$ nodes each update, thus resulting in $\mathcal O(N\log N)$ space and $\mathcal O(N\log^2 N)$ time.

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void setIO(string s = "") {
	cin.tie(0)->sync_with_stdio(0);
	if (s.size()) {
		freopen((s + ".in").c_str(), "r", stdin);
		freopen((s + ".out").c_str(), "w", stdout);
	}