DMOPC '20 Contest 1 P6 - Victor Identifies Software

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 3.0s
Memory limit: 512M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

i mistook math software for a gacha game ~ Victor, 2020

Victor, just like everyone else, has trouble telling the difference between math software and gacha games. As his good friend, you decide to help him overcome this deficiency.

You email him N programs for him to identify. Obviously, he initially assumes they are all gacha games, and declares he will need a_i minutes to test if the ith game is, a gacha game. Sometimes, a_i will be negative. You aren't sure what this means, but unwilling to assume this is a typo, you dutifully note it down.

Victor then sends you Q messages:

  • 1 l r: Victor declares that the l, l+1, \ldots, r-1, rth programs are all gacha games.
  • 2 l r: Victor declares that the l, l+1, \ldots, r-1, rth programs are all math software.
  • 3 l r x: Victor re-evaluates the time he needs to test the l, l+1, \ldots, r-1, rth program: he sets a_l = a_{l+1} = \cdots = a_{r-1} = a_r = x.
  • 4 l r: Victor will test the l, l+1, \ldots, r-1,rth programs, in that order. If he believes the ith game to be a gacha, he will test it for a_i minutes. Otherwise, he will take a break.
  • 5 l r: Victor will test the l, l+1, \ldots, r-1,rth programs, in that order. If he believes the ith game to be math software, he will test it for a_i minutes. Otherwise, he will take a break.

Concerned for Victor's wellbeing, every time he declares he will test some programs, you reply with the longest stretch of time he will spend testing programs without a break.

Note: for type 4 and 5 queries, output breaks galore if none of the programs in the range are gacha or math, respectively. Otherwise, output the longest non-empty stretch of time.

Constraints

For all subtasks, -10^5 \le a_i \le 10^5.

Subtask 1 [5%]

1\leq N, Q\leq 2\,000

Subtask 2 [20%]

1\leq N, Q\leq 300\,000
Victor will never change the amount of time required to test a program. (i.e. no messages of type 3)

Subtask 3 [20%]

1\leq N, Q\leq 300\,000
Victor will change the amount of time required to test exactly 1 program in each query (i.e. a=b for type 3 messages).

Subtask 4 [55%]

1\leq N, Q\leq 300\,000

Input Specification

The first line of input will contain two space-separated integers: N and Q.
The second line of input will contain N space-separated integers: a_1, \ldots, a_N.
The next Q lines will each contain one of Victor's messages.

Output Specification

For each message of the form 4 l r and 5 l r, output the longest stretch of time he will spend testing programs without a break.

Sample Input 1

5 8
5 2 -1 0 5
4 4 4
4 4 5
5 4 4
5 4 5
4 3 3
2 1 3
4 3 3
5 3 3

Sample Output 1

0
5
breaks galore
breaks galore
-1
breaks galore
-1

Sample Input 2

20 13
1 2 5 7 2 8 1 7 -2 3 3 -2 -1 -4 8 -9 10 -5 -2 0
4 8 11
2 9 10
4 8 11
4 17 19
3 12 15 9
5 2 8
1 13 13
2 17 20
4 3 18
5 20 20
4 17 18
3 16 19 -8
5 13 17

Sample Output 2

11
7
10
breaks galore
39
0
breaks galore
-8

Comments

There are no comments at the moment.