oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

globalwarming_ex Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

globalwarming_ex.html

Problem Description

A scientist wants to study how the rising sea level changes the landscape, in particular, how it changes the number of islands. He first investigates one-dimensional worlds. An one-dimensional world is represented by a sequence of positive integers (h0, h1, ..., hn-1), where each integer hi is the altitude at the location i. The following figure depicts an example of such world represented by the sequence (5, 6, 1, 3, 2, 9, 8).

Now, if the sea level is at altitude 2.5, there are 3 islands formed by landmass of the first two columns, the fourth column and the last two columns. Furthermore, if the sea level is at altitude 3.5, there are only 2 islands. When the sea level is altitude x, landmass with altitude x is considered to be submerged under the sea. Hence, if the sea level is at altitude 3, there are 2 islands. Note that having 3 islands is the maximum among all the possible sea levels.

Wait wait wait, doesn't this sound like NOI!? During NOI, the scientist wants to find the maximum number of islands among all sea levels. Thanks to many programmers, he was able to conclude his research on sea levels in one-dimensional worlds. But one-dimensional worlds aren't very common and thus his paper did not get published. Now, he wants to investigate two-dimensional worlds!

Now, instead of a sequence of positive integers, there will be a H x W grid of positive integers not exceeding 2 billion. Similarily, the scientist wants to find the maximum number of islands among all the sea levels.

For clarity, two points belong to the same island when it is possible to reach each other directly or indirectly by going up, down, left or right adjacent points only. (No diagonal)

Input

The first line of input will contain 2 integers, H and W. These are the height and width of the grid of positive integers.

H lines will follow with W integers each. These describe the height of the terrain the scientist is investigating.

Output

Output a single integer, the maximum number of islands among all the sea levels.

Subtasks

Subtask 1 (9%): H = 1, W ≤ 1000. In addition, no point will have a height greater than 1000.

Subtask 2 (8%): H = 1, W ≤ 1000000

Subtask 3 (37%): H ≤ 50, W ≤ 50

Subtask 4 (46%): H * W ≤ 1000000 (There are at most 1000000 integers in the grid)

Subtask 5 (0%): Sample

Sample Input

4 7
5 6 1 3 2 9 8
1 3 2 4 5 7 6
9 1 2 3 4 1 3 
1 2 1 2 1 2 1

Sample Output

4

When the sea level is 1.5m, there will be 4 islands as the following places will be submerged. This is the maximum for all the sea levels.

5 6 x 3 2 9 8
x 3 2 4 5 7 6
9 x 2 3 4 x 3 
x 2 x 2 x 2 x

globalwarming.jpeg

Tags

Data Structure, Union Find Disjoint Set

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1942s128MBMinimum
2882s128MBMinimum
337102s128MBMinimum
446392s128MBMinimum
5012s128MBMinimum

Judge Compile Command

g++-8 ans.cpp -o globalwarming_ex -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.