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 }^{2}N)$

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

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using 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 }^{2}N)$

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

My solution (from a while ago):

1#include<iostream>
2#include<fstream>
3 
4using namespace std;
5 
6typedef pair<int,int> pi;
7 
8#define FOR(i, a, b) for (int i=a; i<b; i++)
9#define F0R(i, a) for (int i=0; i<a; i++)
10 

Solution 3

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