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

collectmushrooms Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

collectmushrooms.html

Problem Description

Peanut owns a mushroom farm and wants to collect some mushrooms. His mushroom farm has N mushrooms in a row, numbered 0 to N-1 from left to right. Each mushroom i has deliciousness Di. Some mushrooms can be rotten, and so can have negative deliciousness. He assigns M minions to help him collect some mushrooms. Each minion i will be assigned a range A to B. Minions tend to fight each other, so Peanut will assign them ranges which do not intersect. However, each minion can only carry at most 1 mushroom, since they have small hands.

Also, minions sometimes rebel and decide to enhance or damage a mushroom. When this happens, the quality of mushroom at X will change to Y.

Help Peanut find the maximum deliciousness each minion can collect. Minions that are collecting mushrooms have to collect 1 mushroom.

Input

The first line contains the number N and M.

The second line contains N numbers, representing the array D.

M lines will follow. The first character of each line will be T.

If T is 0, then it represents a query. 2 integers will then follow, A and B.

If T is 1, then it represents a update. 2 integers will then follow, X, Y.

Output

For each line of query, you are to output the maximum deliciousness of mushrooms collected on a single line.

Limits

For all subtasks: 0 ≤ A≤ B< N, 0 ≤ X < N, |Di, Y| ≤ 109, 0 ≤ T ≤ 1

Subtask 1 (18%): 1 ≤ N, M ≤ 500000, T = 0. There will be no updates. Di = i for all i.

Subtask 2 (29%): 1 ≤ N, M ≤ 500000, T = 0. There will be no updates.

Subtask 3 (53%): 1 ≤ N, M ≤ 500000.

Subtask 4 (0%): Sample Testcases.

Sample Input 1

5 4
3 1 4 2 5
0 0 1
1 1 -3
1 3 6
0 2 4

Sample Output 1

3
6

Explanation

Farm has initial mushroom values: 3 1 4 2 5
Minion picks mushroom at position 0.
Minion damages mushroom 1. Farm has mushrooms values: 3 -3 4 2 5
Minion enhances mushroom 3. Farm has mushroom values: 3 -3 4 6 5
Minion picks mushroom at position 3.

Tags

Syntax

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
118200.5s256MBMinimum
229400.5s256MBMinimum
353610.5s256MBMinimum
4010.5s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o collectmushrooms -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.