HackerEarth Do you order queries? problem solution

In this HackerEarth Do you order queries problem solution You are given n ($1$ $\le$ $n$ $\le$ $300000$) queries. Each query is one of $3$ types:

1. add pair ($a$, $b$) to the set. ($-10^9$ $\le$ $a, b$ $\le$ $10^9$)
2. remove a pair added in query $index$ (All queries are numbered with integers from $1$ to $n$).
3. For a given integer $A$ find the maximal value $a·A + b$ over all pairs ($a$, $b$) from the set. ($-10^9$ $\le$ $A$ $\le$ $10^9$). It is guaranteed that the set of pair will not be *empty*.

HackerEarth Do you order queries? problem solution.

# include <bits/stdc++.h>

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

inline void Input_Output () {
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 3e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 6e7 + 1;
const int N = 5e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n, m, k;

int op[N];
int a[N], b[N];
using pt = pair<int, int>;
pt bad = {-inf, -inf};
pt t[mxn];
int rt[N*4];
int L[mxn];
int R[mxn];
int Ptr;

int arr[N];
int ptr;

ll f (pt a, int x) {
    if (a == bad) return -INF;
    return a.first * (ll)x + a.second;
}

void upd (int &v, int _v, pt nw, int tl = 1, int tr = ptr) {
    v = ++Ptr;

    if(!_v) {
        t[v] = nw;
        return;
    }

    t[v] = t[_v];
    if (tl == tr) {
        if (f(t[v], arr[tl]) < f(nw, arr[tl])) t[v] = nw;
        return;
    }

    int tm = (tl + tr) >> 1;
    if (t[v].F > nw.F) swap(t[v], nw);

    if (f(t[v], arr[tm+1]) < f(nw, arr[tm+1])) {
        swap(t[v], nw);
        upd (L[v], L[_v], nw, tl, tm);
        R[v] = R[_v];
    } else {
        upd (R[v], R[_v], nw, tm+1, tr);
        L[v] = L[_v];
    }
    
}

ll get (int x, int v, int tl = 1, int tr = ptr) {
    int tm = (tl + tr) >> 1;
    if (!v) return -INF;
    if (t[v] == bad) return -INF;

    if (tl == tr) {
        return f(t[v], x);
    }
    if (x <= arr[tm]) {
        return max(f(t[v], x), get(x, L[v], tl, tm));
    }

    return max(f(t[v], x), get(x, R[v], tm+1, tr));
}


namespace DC {
    vector < int > q[N * 4];

    void add (int l, int r, int id, int v = 1, int tl = 1, int tr = n) {
        if (l > tr || tl > r) return;
        if (tl >= l && tr<= r) {
            q[v].pb(id);
            return;
        }

        int tm = (tl + tr) >> 1;

        add(l, r, id, v<<1, tl, tm);
        add(l, r, id, v<<1|1, tm+1, tr);
    }

    void go (int v = 1, int tl = 1, int tr = n) {
        rt[v] = rt[v/2];
        int tm = (tl+tr)>>1;
        
        //sort(every(q[v]), [&] (int x, int y) { return mp(-a[x], -b[x]) < mp(-a[y], -b[y]); });
        for (auto it : q[v]) {
            //cout << "+ " << it << '\n';
            int old = rt[v];
            upd (rt[v], old, {a[it], b[it]});
        }
        q[v].clear();
        q[v].shrink_to_fit();

        if (tl == tr) {
            if(op[tl] == 3) {
            //  cout << "solving: " << tl << '\n';
                ll res = get(a[tl], rt[v]);
                assert(res != -INF);
                cout << res << '\n';
            }
            return;
        }

        
        go(v<<1, tl, tm);
        go(v<<1 | 1, tm+1, tr);
        
        
    }

    inline void solve () {
        ptr = 0;
        For (i, 1, n) if (op[i] != 2) {
            arr[++ptr] = a[i];
        }
        sort(arr + 1, arr + ptr + 1);
        ptr = unique(arr + 1, arr + ptr + 1) - arr - 1;

        Ptr = 0;
        go();
    }
}


bool was[N];

int main () {
    SpeedForce;
    
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        cin >> op[i] >> a[i];
        if (op[i] == 1) cin >> b[i];
        else if (op[i] == 2) {
            DC::add(a[i] + 1, i - 1, a[i]);
            was[a[i]] = 1;
        }
    }
    For (i, 1, n) if (op[i] == 1) {
        if(!was[i]) {
            DC::add(i + 1, n, i);
        }
    }

    DC:: solve();



    return Accepted;
}