Codeforce Round #576 Question B

The questions is
There is a country with n citizens. The i-th of them initially has ai

money. The government strictly controls the wealth of its citizens. Whenever a citizen makes a purchase or earns some money, they must send a receipt to the social services mentioning the amount of money they currently have.

Sometimes the government makes payouts to the poor: all citizens who have strictly less money than x

are paid accordingly so that after the payout they have exactly x

money. In this case the citizens don’t send a receipt.

You know the initial wealth of every citizen and the log of all events: receipts and payouts. Restore the amount of money each citizen has after all events.

My code for the questions is ,

   def fun(l,a,n):
    for i in range(n):
        if a[i]<=l[1]:
            a[i]=l[1]
def fun2(l,a,n):
    a[l[1]-1]=l[2]

n=int(input())
a=list(map(int,input().split()))
#q=int(input())
for _ in range(int(input())):
    l=list(map(int,input().split()))
    if l[0]==2:
        fun(l,a,n)
    else:
        fun2(l,a,n)
print(*a) 

but my code is exceeding time limit ,any suggestions or improvement in the code.?

Here by Observation we can say :
if(Query 1) : No matter what was previous value/query, it’s going to make change at arr[p];
if we operate Query 1 on same ‘p’ again and again we need to consider only
the recent update at arr[p] = x;
if(Query 2) : If we don’t operate Query 1 on any index, ans for that index will always be
maximum value of ‘x’ of all Query 2;

So we can travel Queries array in reverse. if we occur Query 1 then we change value at ‘p’ to
max(Query 1 x, MX) where MX will max value of Query 2 ‘x’ uptill the point we are at currently. Also we won’t visit again at same ‘p’, i.e vis[p]=1;
if Query 2 occurs we can check if MX remains same or get an update.
Lastly print ans as if(vis[i]) arr[i], else max(MX,arr[i]); // becuz MX will have Highest of all
‘x’ of Query 2;

You might understand better by reading code - https://ideone.com/ONvxGr

Its hard to get the logic behind the problem , can you explain why have you choosesn approaching the problem the way you just said …?