Covered Segment Length (APCS 2016-03 Advanced)

1.0s 256M

Given several segments on a one-dimensional axis, find the total length they cover. Overlapping parts are counted only once.

For example, given \(4\) segments \((5, 6)\), \((1, 2)\), \((4, 8)\), \((7, 9)\) as shown below, the covered length is \(6\).

Input

The first line contains a positive integer \(N\), the number of segments.

Each of the next \(N\) lines contains the integer coordinates of a segment's start point \(L\) and end point \(R\), separated by one space. The start coordinate is less than or equal to the end coordinate.

  • 30% of the test data satisfy \(N < 100\), \(0 \le L, R < 1000\), and no two segments overlap.
  • 70% of the test data satisfy \(N < 100\), \(0 \le L, R < 1000\); segments may overlap.
  • 100% of the test data satisfy \(N < 10000\), \(0 \le L, R < 10000000\); segments may overlap.

Output

Output the total covered length.

Sample Input 1

5
160 180
150 200
280 300
300 330
190 210

Sample Output 1

110

Sample Input 2

1
120 120

Sample Output 2

0

Source

APCS March 2016, programming problem 3 "Covered Segment Length"; also available as ZeroJudge b966.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.