Official Analysis (C++)

Due to the low bounds on NN, we can naively simulate the events. We'll sort by arrival time to process the cows in order and store the cows that are waiting in a priority queue.

Implementation

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

C++

#include <algorithm>
#include <array>
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>


using namespace std;


int main() {

Java

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


public class Convention2 {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("convention2.in"));


		int cowNum = Integer.parseInt(read.readLine());
		Cow[] cows = new Cow[cowNum];
		for (int c = 0; c < cowNum; c++) {

Python

import heapq


cows = []
with open("convention2.in") as read:
	for c in range(int(read.readline())):
		start, duration = [int(i) for i in read.readline().split()]
		cows.append((c, start, duration))


# sort by arrival time
cows.sort(key=lambda c: c[1])

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