Table of Contents

ExplanationImplementation

Official Analysis (C++)

Explanation

In a crossing pair, the two cows must be of the form 12121212. We can reword this as:

Given a start and an end point, find the number of cows which start (but don't end) within that range.

We can query these ranges with a sum segment tree by processing all 2n2n points and keeping track of active cows (cows which have started but not ended).

Implementation

Time Complexity: O(Nlog⁡N)\mathcal{O}(N\log N)

C++

#include <cstdio>
#include <iostream>
#include <map>
#include <vector>


using std::vector;


 Code Snippet: Segment Tree Implementation (Click to expand)


int main() {

Java

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


public class CircleCross {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(new File("circlecross.in"));
		PrintWriter out = new PrintWriter("circlecross.out");


		int n = sc.nextInt();
		int[] points = new int[n * 2];

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