# 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;}`