Official Editorial (C++)

Solution 1: Coordinate Compression

Due to the large constraints on lil_i and rir_i, it is impossible to brute force the number of intersecting segments for each point on the coordinate line. However, notice that we can compress the coordinates and "pretend" as if the coordinates were between 11 and nn.

This allows us to apply prefix sums on each point in our compressed number line and retransform these compressed coordinates to the original endpoints lil_i and rir_i. To compress the coordinates, we can either sort the coordinates or use an ordered map.

Implementation

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

C++

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


using ll = long long;


int main() {
	int n;
	cin >> n;
	// This stores the original endpoints to use in our frequency array later
	vector<pair<ll, ll>> segments(n);

Java

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


public class CoveredPointsCount {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());


		Pair[] segments = new Pair[n];
		// This stores only the unique endpoints in sorted order

Python

n = int(input())
# This stores the original endpoints to use in our frequency array later
segments = []


# This stores only the unique endpoints in sorted order
points = set()


for _ in range(n):
	l, r = map(int, input().split())
	segments.append((l, r))

Solution 2: Map

Alternatively, we can also use a map to store frequencies at each point of interest and iterate through them in order. This way, we don't need to explicitly perform the coordinate compression.

Implementation

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

C++

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


using ll = long long;


int main() {
	int n;
	cin >> n;


	// distinct coordinates of the start and end of the segments

Python

from collections import defaultdict


n = int(input())


points = set()  # distinct coordinates of the start and end of the segments
freq = defaultdict(int)  # frequency of a given coordinate


for _ in range(n):
	l, r = map(int, input().split())

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