L. All’s Wall That Ends Wall

Codeforces

IDCF10135L

Time3000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

In the magical forest, you come upon N walls that you think is a great place to store water for your animal friends. The ith wall consists of ai blocks stacked on top of each other. Your job is to answer queries of two types: - For queries of the first type, print the amount of water that could be stored between all the walls. - For queries of the second type, increase the number of blocks on the xth wall by v. The first line of input is T – the number of test cases. The first line of each test case is integers N and Q (1 ≤ N, Q ≤ 105). The second line contains N space-separated integers ai (1 ≤ ai ≤ 105). The next Q lines contain either ‘P’ – denoting a query of the first type, or ‘U’ followed by x and v – denoting a query of the second type (1 ≤ x ≤ N) (1 ≤ v ≤ 104). For each test case and query of the first type, output on a line the amount of water that could be stored between the walls. ## Input The first line of input is T – the number of test cases.The first line of each test case is integers N and Q (1 ≤ N, Q ≤ 105).The second line contains N space-separated integers ai (1 ≤ ai ≤ 105).The next Q lines contain either ‘P’ – denoting a query of the first type, or ‘U’ followed by x and v – denoting a query of the second type (1 ≤ x ≤ N) (1 ≤ v ≤ 104). ## Output For each test case and query of the first type, output on a line the amount of water that could be stored between the walls. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case: - Let $ N \in \mathbb{Z} $ be the number of walls. - Let $ Q \in \mathbb{Z} $ be the number of queries. - Let $ A = (a_1, a_2, \dots, a_N) $ be a sequence of non-negative integers representing the height of each wall. **Constraints** 1. $ 1 \leq T \leq \text{unspecified} $ 2. For each test case: - $ 1 \leq N, Q \leq 10^5 $ - $ 1 \leq a_i \leq 10^5 $ for all $ i \in \{1, \dots, N\} $ - For update queries: $ 1 \leq x \leq N $, $ 1 \leq v \leq 10^4 $ **Operations** - **Type P (Query)**: Compute the total trapped water between walls: $$ W = \sum_{i=1}^{N} \left( \min\left( \max_{j=1}^{i-1} a_j, \max_{j=i+1}^{N} a_j \right) - a_i \right)^+ $$ where $ (x)^+ = \max(0, x) $. - **Type U (Update)**: Update $ a_x \leftarrow a_x + v $. **Objective** For each query of type P, output the value of $ W $ as defined above.

API Response (JSON)

{
  "problem": {
    "name": "L. All’s Wall That Ends Wall",
    "description": {
      "content": "In the magical forest, you come upon N walls that you think is a great place to store water for your animal friends. The ith wall consists of ai blocks stacked on top of each other. Your job is to ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10135L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In the magical forest, you come upon N walls that you think is a great place to store water for your animal friends. The ith wall consists of ai blocks stacked on top of each other.\n\nYour job is to an...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N \\in \\mathbb{Z} $ be the number of walls.  \n- Let $ Q \\in \\mathbb{Z} $ be the number of queries...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments