CCOQR '16 - Data Structure

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.4s
Memory limit: 64M

Problem types

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 \le N \le 10^9) rows, numbered 1 \dots N from top to bottom. Each row r has r block spaces, which are labelled (r, 1) \dots (r, r) from left to right. Each block space (r, c) in rows 1 \dots (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 \le M \le 10^5) different block spaces which must contain data - the i^{th} of these is block space (r_i, c_i) (1 \le c_i \le r_i \le N). All of the other block spaces in the pyramid may either be filled with arbitrary 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.


  • For 3 of the 15 marks available, N \le 100 and M \le 200.
  • For another 3 of the 15 marks available, N \le 2\,000 and M \le 10^5.
  • For another 3 of the 15 marks available, N \le 10^9 and M \le 2.

Input Specification

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 \dots M.

Output Specification

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

Output for Sample Input


Explanation for Output for Sample Input

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.


  • 1
    Evan_Yu123  commented on Nov. 2, 2017, 1:59 p.m.

    Is it guaranteed that the answer can be stored in a 64 bit integer? What if the test case is 10e9 1 1 1 ?

    • 1
      Kirito  commented on Nov. 2, 2017, 4:59 p.m.

      The answer to that case is on the order of 5 \times 10^{17}, which fits in a 64-bit integer.

      • 1
        Evan_Yu123  commented on Nov. 2, 2017, 7:32 p.m.

        Sorry im dumb, i think i typed 2^54 into my calculator earlier

        • 2
          Kirito  commented on Nov. 3, 2017, 1:33 a.m.

          10e9 is actually 10^{10}, 1e9 is 10^9. That might be why.

          • 4
            Evan_Yu123  commented on Nov. 3, 2017, 12:32 p.m.

            UGHH whats wrong with me, thx for all ur help

  • 30
    ImbaCalvin  commented on Dec. 13, 2016, 6:16 p.m.

    How is this a data structure problem?

  • 9
    moladan123  commented on March 25, 2016, 1:55 p.m.

    Is anyone interested in making editorials for these ccoqr problems?