Egoism

AtCoder

IDabc440_f

Time2000ms

Memory256MB

Difficulty—

> At AtCoder Ranch, horses bathe themselves. Some horses clean up afterward, while others leave a mess. There are $N$ horses, numbered $1$ to $N$. Horse $i$ ($1 \leq i \leq N$) has a **mood** $A_i$ and a **tidiness** $B_i$ (where $B_i$ is $1$ or $2$). At night, the $N$ horses bathe once each. Let $p_j$ be the number of the horse that bathes in the $j$\-th turn ($1 \leq j \leq N$). The **satisfaction** of horse $p_j$ is given as follows: * If $j \geq 2$, the product of the mood of horse $p_j$ and the tidiness of horse $p_{j-1}$. * If $j = 1$, the mood of horse $p_j$. You will be given $Q$ queries, one for each day over $Q$ days. Process them in order. The query for the $k$\-th day ($1 \leq k \leq Q$) is as follows: * Change the mood of horse $W_k$ to $X_k$ and its tidiness to $Y_k$ (where $Y_k$ is $1$ or $2$). Then, find the maximum possible total satisfaction of the $N$ horses' baths that night if you can decide the order in which the $N$ horses bathe arbitrarily. ## Constraints * $1 \leq N \leq 2 \times 10^5$ * $1 \leq Q \leq 2 \times 10^5$ * $1 \leq A_i \leq 10^6$ ($1 \leq i \leq N$) * $B_i$ is $1$ or $2$. ($1 \leq i \leq N$) * $1 \leq W_k \leq N$ ($1 \leq k \leq Q$) * $1 \leq X_k \leq 10^6$ ($1 \leq k \leq Q$) * $Y_k$ is $1$ or $2$. ($1 \leq k \leq Q$) * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $Q$ $A_1$ $B_1$ $\vdots$ $A_N$ $B_N$ $W_1$ $X_1$ $Y_1$ $\vdots$ $W_Q$ $X_Q$ $Y_Q$ [samples]

Samples

Input #1

4 4
1 2
10 1
3 1
7 2
2 7 1
1 3 1
2 2 1
3 1000000 2

Output #1

32
27
18
2000015

For the query on the first day, if the horses bathe in the order $3,1,4,2$, the satisfaction of each horse is as follows:

*   Horse $3$'s satisfaction is $3$
*   Horse $1$'s satisfaction is $1 \times 1 = 1$
*   Horse $4$'s satisfaction is $7 \times 2 = 14$
*   Horse $2$'s satisfaction is $7 \times 2 = 14$

The total satisfaction in this case is $32$.
For the query on the second day, if the horses bathe in the order $4,2,1,3$, the satisfaction of each horse is as follows:

*   Horse $4$'s satisfaction is $7$
*   Horse $2$'s satisfaction is $7 \times 2 = 14$
*   Horse $1$'s satisfaction is $3 \times 1 = 3$
*   Horse $3$'s satisfaction is $3 \times 1 = 3$

The total satisfaction in this case is $27$.
For the query on the third day, if the horses bathe in the order $4,3,2,1$, the total satisfaction is $18$.
For the query on the fourth day, if the horses bathe in the order $4,3,1,2$, the total satisfaction is $2000015$.

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Egoism",
    "description": {
      "content": "> At AtCoder Ranch, horses bathe themselves. Some horses clean up afterward, while others leave a mess. There are $N$ horses, numbered $1$ to $N$. Horse $i$ ($1 \\leq i \\leq N$) has a **mood** $A_i$ a",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc440_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "> At AtCoder Ranch, horses bathe themselves. Some horses clean up afterward, while others leave a mess.\n\nThere are $N$ horses, numbered $1$ to $N$. Horse $i$ ($1 \\leq i \\leq N$) has a **mood** $A_i$ a...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments