Different queries
Tag(s):

Algorithms, Easy, Merge sort, Sorting

Problem
Editorial
Analytics

You are given an array $A$ of size $N$. You have to perform $Q$ queries on the array. Each of these queries belongs to the following types of queries:

1. $L$ $R$ $X$ : Add $X$ to all elements in the range $[L, R]$
2. $L$ $R$ $X$ : Set the value of all elements in the range $[L, R]$ to $X$

However, it is not mandatory to perform the queries in order. Your task is to determine the lexicographically largest array that can be obtained by performing all the $Q$ queries.

Note:

• The queries cannot be changed or skipped. You can only change the order in which they are performed.
• If there exists an index $i$ such than $A_i > B_i$ and $A_j = B_j$ for all $1 \le j < i$, then the array $A$ is lexicographically larger than an array $B$.

Input format

• First line: Two space-separated integers $N$ and $Q$

• Next line: $N$ space-separated integers denoting the array $A$

• Next $Q$ lines: The queries to be performed of the $type$ $L$ $R$ $X$

Output format

Print $N$ space-separated integers that denote the lexicographically largest array that can be obtained as mentioned in the problem statement.

Constraints

$1 \le N \le 500$

$1 \le Q \le 10^5$

$type \in \{1, 2\}$

$1 \le L \le R \le N$

$-10^5 \le X, A_i \le 10^5$

SAMPLE INPUT
5 3
1 2 3 4 5
1 3 4 2
2 1 2 3
1 4 5 -6
SAMPLE OUTPUT
3 3 5 0 -1
Explanation

In this case, the order in which the queries are performed does not matter. Assuming the queries are performed in the same order as the input, the array after each query is as follows:

Initially, $[ 1, 2, 3, 4, 5 ]$

After query 1, $[1, 2, 5, 6, 5]$

After query 2, $[3, 3, 5, 6, 5]$

After query 3, $[3, 3, 5, 0, -1]$

Observe that the final array would have been same even if the queries were performed in some other order.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

This Problem was Asked in Challenge Name

December Easy' 18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Advanced Algorithms
• Algorithms > Dynamic Programming
• Basic Programming > Implementation
• Data Structures > Trees