All Tracks Data Structures Advanced Data Structures Problem

Alice and friends
Tag(s):

Data Structures, Hard, Segment Trees

Problem
Editorial
Analytics

Alice and her friends are playing a game. There is a big rectangle field with $$n$$ rows and $$m$$ columns initially with empty cells. Every turn Alice puts a small cube in one of the empty cells. After this friends need to find a empty cell so that they can see the maximum number of empty cells from it. Empty cell $$A$$ can be seen from empty cell $$B$$ if they are in the same row or in the same column and there are no cubes between them. Help Alice to check the answers her friends made. After each step find the maximum number of cells which can be seen from one free cell on the field.

$$INPUT$$

The first line of the input contains three integers $$n$$, $$m$$ and $$q$$ $$(1 \leq n, m \leq 50 000, 1 \leq q \leq min(n \cdot m - 1, 100 000))$$ - number of rows, number of columns and number of game steps.

Then following $$q$$ lines contain description of the turns. The $$i$$-th of these lines contains two integers $$r_i$$ and $$c_i$$ - row number and column number of cell where Alice put a cube in this turn. It is guaranteed that this cell is free before this turn.

$$OUTPUT$$

Output q lines. The $$i$$-th of these lines should contain single integer - the maximum number of cells that can be seen from some free cell on field after $$i$$-th step.

SAMPLE INPUT
4 5 6
2 1
1 2
3 3
4 4
1 5
2 4
SAMPLE OUTPUT
8
8
8
7
6
5
Explanation

Lets define cell on the intersection of $$r$$-th row and $$c$$-th column as $$(r, c)$$. Cells with maximum answer after each query in sample:

  1. $$(4, 5)$$ - answer 8
  2. $$(4, 5)$$ - answer 8
  3. $$(4, 5)$$ - answer 8
  4. $$(2, 5)$$ - answer 7
  5. $$(2, 5)$$ - answer 6
  6. $$(4, 2)$$ - answer 5
Time Limit: 4.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications