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

3.9

15 votes
Algorithms, Easy, Merge sort, Sorting
Problem

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

  1.    : Add  to all elements in the range 
  2.    : Set the value of all elements in the range  to 

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 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  such than  and  for all , then the array  is lexicographically larger than an array .

Input format

  • First line: Two space-separated integers  and 

  • Next line:  space-separated integers denoting the array 

  • Next  lines: The queries to be performed of the    

Output format

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

Constraints

 

 

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, 

After query 1, 

After query 2, 

After query 3, 

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

Contributers:
Editor Image

?