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


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