2016 Canadian Computing Olympiad Qualifying Round

Problem Q3: Data Structure

It's a well-known fact that, inside computers, all data is stored in 2D pyramids of data blocks.

A certain pyramid has N (1 ≤ N ≤ 10⁹) rows, numbered 1..N from top to bottom. Each row r has r block spaces, which are labelled (r, 1)..(r, r) from left to right. Each block space (r, c) in rows 1..(N − 1) rests on top of two supporting block spaces in the row below it – block spaces (r + 1, c) and (r + 1, c + 1). For example, a pyramid with 6 rows is illustrated below, with block spaces (3, 1), (4, 4), and (6, 2) indicated in red:

Now, each block space may either contain data, or be empty. A block space containing data is only stable if it's in the bottom row (row N), or if both of its two supporting block spaces also contain data. The entire pyramid is only stable if all of its non-empty block spaces are stable.

You know that there are M (1 ≤ M ≤ 10⁵) different block spaces which must contain data – the i-th of these is block space (r_i, c_i) (1 ≤ c_i ≤ r_i ≤ N). All of the other block spaces in the pyramid may either be filled with abitrary data or be left empty. However, everyone knows that data is expensive. As such, you're interested in the smallest amount of data that the pyramid's block spaces can contain such that at least the M required block spaces contain data, and the entire data structure is stable.

Subtasks

For 3 of the 15 marks available, N ≤ 100 and M ≤ 200.
For another 3 of the 15 marks available, N ≤ 2000 and M ≤ 10⁵.
For another 3 of the 15 marks available, N ≤ 10⁹ and M ≤ 2.

Input Format

The first line of the input contains two integers, N and M. The remaining M lines each contain two integers, r_i and c_i for i = 1..M.

Output Format

Output a single integer, the minimum number of block spaces which can contain data such that the entire pyramid is stable. Note that this value may not fit in a 32-bit signed integer, and may need to be stored in a long long / long / int64 variable in C++ / Java / Pascal, respectively.

Sample Input

6 3
3 1
4 4
6 2

Sample Output

15

Explanation

The diagram below illustrates the pyramid described by the sample case, where the 3 red block spaces must contain data, while the 12 orange block spaces represent the optimal set of blocks to additionally fill with data to make the entire pyramid stable.

All Submissions
Best Solutions

Point Value: 17 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Mar 09, 2016
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I think there's some mistake in test case 4:ad as identical solutions for the problem fails here on test case 4:ad but passes on dmoj

Thanks for the report. You're correct; there was a problem with test case 4ad. I've rectified it and am in the process of manually rejudging submissions.

Edit: I've rejudged at least one submission for each user to whom this would make a difference.