Max Matrix

AtCoder

IDjsc2021_f

Time3000ms

Memory256MB

Difficulty—

We have a sequence $a$ of length $N$ and a sequence $b$ of length $M$. Initially, every element in $a$ and $b$ is $0$. You are asked to process $Q$ queries. In the $i$\-th query, given three integers $T_i$, $X_i$, and $Y_i$, do the following: * if $T_i = 1$: replace $a_{X_i}$ with $Y_i$; * if $T_i = 2$: replace $b_{X_i}$ with $Y_i$. Then, after processing each query, print the value $\displaystyle \sum_{i = 1}^N \sum_{j = 1}^M \max(a_i, b_j)$. ## Constraints * $1 \le N \le 2 \times 10^5$ * $1 \le M \le 2 \times 10^5$ * $1 \le Q \le 2 \times 10^5$ * $T_i$ is $1$ or $2$. * If $T_i = 1$, $1 \le X_i \le N$. * If $T_i = 2$, $1 \le X_i \le M$. * $1 \le Y_i \le 10^8$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $M$ $Q$ $T_1$ $X_1$ $Y_1$ $T_2$ $X_2$ $Y_2$ $T_3$ $X_3$ $Y_3$ $\hspace{21pt} \vdots$ $T_Q$ $X_Q$ $Y_Q$ [samples]

Samples

Input #1

Output #1

20
50
55
85

If we write $\max(a_i, b_j)$ at the $i$\-th row and $j$\-th column in a grid, the four queries will change it as follows: ![image](https://img.atcoder.jp/ghi/9a4098e2aa50b21c51ce3664d278ba87.png)

Input #2

Output #2

Input #3

200000 200000 4
2 112219 100000000
1 73821 100000000
2 26402 100000000
1 73821 100000000

Output #3

20000000000000
39999900000000
59999800000000
59999800000000

The integers to be printed may not fit into a $32$\-bit integer type.

API Response (JSON)

{
  "problem": {
    "name": "Max Matrix",
    "description": {
      "content": "We have a sequence $a$ of length $N$ and a sequence $b$ of length $M$. Initially, every element in $a$ and $b$ is $0$.   You are asked to process $Q$ queries. In the $i$\\-th query, given three integer",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "jsc2021_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have a sequence $a$ of length $N$ and a sequence $b$ of length $M$. Initially, every element in $a$ and $b$ is $0$.  \nYou are asked to process $Q$ queries. In the $i$\\-th query, given three integer...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments