All Tracks>Algorithms> Sorting> Merge Sort> Problem
Different queries
★★★★★

3.9

15 votes
Algorithms, Easy, Merge sort, Sorting
Problem

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 Ai>Bi and Aj=Bj for all 1≤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≤N≤500

1≤Q≤105

type∈{1,2}

1≤L≤R≤N

−105≤X,Ai≤105

 

 

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
Time Limit: 1
Memory Limit: 256
Source Limit:
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.

Contributers:
Editor Image

?