All Tracks Data Structures Arrays 1-D Problem

Not in Range
/

Arrays, Data Structures, One-dimensional, Partial Sum, Prefix sum, Segment Trees

Problem
Editorial
Analytics

You are given \(10^6\) boxes that are numbered from \(1\) to \(10^6\). The value of each box is equal to its number. 
There are \(N\) ranges and every range consists of two integers \(L\)  and \(R\)  denoting that the value of box in the range \([L,R] \) will turn out to be zero. 
Find the sum of values of all boxes from \(1\) to \(10^6\) .

Note: The ranges may overlap.

Input format

  • First line: Integer \(N\)
  • Next N lines: Two space-separated integers \(L\) and \(R\)  

Output format
Print a single integer denoting the answer.

Constraints
\(0 ≤ N ≤ 10^5 \)
\(1 ≤  L ≤ R ≤ 10^6 \)

SAMPLE INPUT
5
2 20
23 200
21 21
101 2000
2002 999998
SAMPLE OUTPUT
2002023
Explanation

Boxes having number 1, 22, 2001, 999999,1000000 does not belong to any range.
So the sum of these numbers is 2002023 which is our answer.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?