1199D - Welfare State - CodeForces Solution

// Jay Maa Chamunda
/*
Author: Sahil Anand
Find Me on: https://linktr.ee/sahilanand30
*/
/*-----------------------------{HEADERS}-----------------------------*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
/*--------------------------{Optimizations}--------------------------*/
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
/*------------------------------{INLINE MACROS}------------------------------*/
#define ll long long int
#define rep(i, n) for (ll i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define ull unsigned long long int
#define countSetBits(z) __builtin_popcountll(z);
#define vll vector<long long int>
#define LL_MAX __LONG_LONG_MAX__
#define LL_MIN -9223372036854775808
#define PI 3.1415926536
#define mod 1000000007
#define INF 1e18
#define nl endl
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define maxHeap priority_queue<ll>                   // maxElement at the top
#define minHeap priority_queue<ll, vll, greater<ll>> // minElement at the top
#define printWithPrecision(i, x) cout << fixed << setprecision(i) << x << nl
/*----------------------------{PBDS/ORDERED_SET}----------------------------*/
typedef tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> pbds;
/*----------------------------{NON-STANDARD I/O}----------------------------*/
#define not_standard                  \
    freopen("input.txt", "r", stdin); \
    freopen("output.txt", "w", stdout);
/*-------------------------------{FAST I/O}-------------------------------*/
#define FASTIO                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);
/*--------------------------------{MAIN CODE}--------------------------------*/
ll getMax(map<ll,ll>&upcomming_payoff){
    auto it=--upcomming_payoff.end();
    return (it->first);
}
int main()
{
    FASTIO
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        ll n,q,x,p,type,mx=-1;
        cin>>n;
        vll a(n);
        vector<bool>seen(n);
        rep(i,n){
            seen[i]=false;
            cin>>a[i];
        }
        cin>>q;
        vector<vll>queries;
        map<ll,ll>upcomming_payoff;
        while(q--)
        {
            cin>>type;
            if(type==1)// recept
            {
                cin>>p>>x;
                seen[p-1]=true;
                queries.push_back({1,p-1,x});
            }
            else //payoff
            {
                cin>>x;
                mx=max(mx,x);
                queries.push_back({2,x});
                upcomming_payoff[x]++;
            }
        }
        for(auto val : queries){
            type=val[0];
            if(type==1){
                p=val[1],x=val[2];
                if(upcomming_payoff.empty())a[p]=x;
                else if(x<=getMax(upcomming_payoff)){
                    a[p]=getMax(upcomming_payoff);
                }
                else{
                    a[p]=x;
                }
            }
            else{
                x=val[1];
                upcomming_payoff[x]--;
                if(upcomming_payoff[x]==0)upcomming_payoff.erase(x);
            }
        }
        rep(i,n)if(!seen[i] && a[i]<mx)a[i]=mx;
        rep(i,n)cout<<a[i]<<' ';
        cout<<nl;
    }
    return 0;
}
/*
Logic:-
1. Here we will bifurcate the people in two groups, one who will give recept. And another will not give recept, hence in the end these second type of group will possess money same as initial money but the only thing is they will have money greater than or equal to the 'maximum' payoff that had been announced by the government.
2. And the first type of people who gives recept will only have money as announced iff there no payoff ahead of it which is greater than what they've said.
*/