USACO 2017 February Contest, Gold Problem 3 - Why Did the Cow Cross the Road III
Algorithm Used: Range Queries, Segment Tree
Treat the cow entry and exit points as the beginning and ending of ranges.
/* 1. for each cow, create a range, such that cow i enters at point a and exits
at point b the range for this cow will be (a, b)
2. sort the ranges based on starting point to make it easier to count number
of overlapping ranges
3. create a segment tree
4. iterate over the ranges, and create a difference array storing the ranges
since the ranges are added one by one, use a segment tree to store the
difference array so that it can be updated quickly and sum queries can
also be done quickly
5. For each range, figure out the number of ranges that it overlaps with
To do this, find out the number of ranges that start before the
current range using a sum query. Then find out the number of ranges
that end after the current range using another sum query. The
difference of these two numbers will give the number of ranges that
overlap with the current range, such that the current range starts after
all other ranges.
ILLUSTRATION
[range being compared]
[current range]
There is no need to count number of overlapping ranges
such that the current range starts before other ranges (check below
illustration), since those will be covered by latter ranges.
ILLUSTRATION
[current range]
[range being compared]
Why add the ranges one by one? - To avoid the counting the same overlapping
ranges more than once.
*/
#include <bits/stdc++.h>
using namespace std;
vector <int> seg_tree;
int seg_size;
int sum(int a, int b){
a += seg_size;
b += seg_size;
int s = 0;
while (a <= b){
if (a % 2 == 1)
s += seg_tree[a++];
if (b % 2 == 0)
s += seg_tree[b--];
a /= 2;
b /= 2;
}
return s;
}
void update(int x, int s){
x += seg_size;
seg_tree[x] += s;
for (x /= 2; x >= 1; x /= 2)
seg_tree[x] = seg_tree[x*2] + seg_tree[x*2+1];
}
int main()
{
freopen("circlecross.in", "r", stdin);
freopen("circlecross.out", "w", stdout);
int n;
cin >> n;
vector <int> cows(2 * n);
vector <pair <int, int>> ranges(n, {-1, -1});
for (int i = 0; i < 2 * n; i++){
cin >> cows[i];
if (ranges[cows[i]-1].first == -1)
ranges[cows[i]-1] = {i, -1};
else
ranges[cows[i]-1] = {ranges[cows[i]-1].first, i};
}
sort(begin(ranges), end(ranges));
seg_size = pow(2, ceil(log2(n*2)));
seg_tree.resize(seg_size * 2);
vector <int> overlapping_ranges(n);
for (int i = 0; i < n; i++){
int a = ranges[i].first, b = ranges[i].second;
int no_of_ranges_started_before_curr = sum(0, a-1);
int no_of_ranges_ended_after_curr = abs(sum(b+1, seg_size-1));
overlapping_ranges[i] = no_of_ranges_started_before_curr - no_of_ranges_ended_after_curr;
update(a, 1);
update(b, -1);
}
int ans = 0;
for (auto i : overlapping_ranges)
ans += i;
cout << ans << '\n';
return 0;
}
Comments