[Codeforces] F. Lena and Queries

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : F. Lena and Queries
Source            : Codeforces
Category          : Data Structure, Dynamic Programing
Algorithm         : Dynamic Connectivity, DP Optimization
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll            long long int  
#define endl          '\n'  
#define pll           pair <ll, ll>  
#define mk            make_pair  
  
static const int maxn = 4e5 + 5;  
static const ll is_query = LLONG_MIN;  
  
struct Line  
{  
      ll m, b;  
      mutable function <const Line*()> succ;  
      bool operator < (const Line &rhs) const  
      {  
            if (rhs.b != is_query) return m < rhs.m;  
            const Line *s = succ();  
            if (!s) return 0;  
            ll x = rhs.m;  
            return (b - s->b) < ((s->m - m) * x);  
      }  
};  
  
struct CHT : public multiset <Line>  
{  
      bool bad(iterator y)  
      {  
            auto z = next(y);  
            if (y == begin())  
            {  
                  if (z == end()) return 0;  
                  return y->m == z->m && y->b <= z->b;  
            }  
            auto x = prev(y);  
            if (z == end()) return y->m == x->m && y->b <= x->b;  
            return 1.0 * (x->b - y->b) * (z->m - y->m) >= 1.0 * (y->b - z->b) * (y->m - x->m);  
      }  
      void add(ll m, ll b)  
      {  
            auto y = insert({m, b});  
            y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };  
            if (bad(y)) { erase(y); return; }  
            while (next(y) != end() && bad(next(y))) erase(next(y));  
            while (y != begin() && bad(prev(y))) erase(prev(y));  
      }  
      ll query(ll x)  
      {  
            auto l = *lower_bound((Line){x, is_query});  
            return l.m * x + l.b;  
      }  
};  
  
vector < vector <pll> > Tree(4 * maxn);  
  
void update(int node, int a, int b, int i, int j, pll p)  
{  
      if (a > j or b < i) return;  
      if (a >= i and b <= j) return void(Tree[node].push_back(p));  
      int lchild = node * 2;  
      int rchild = lchild + 1;  
      int mid = (a + b) / 2;  
      update(lchild, a, mid, i, j, p);  
      update(rchild, mid + 1, b, i, j, p);  
}  
  
vector < CHT* > cht(30);  
vector <ll> qval(maxn);  
vector <bool> valid(maxn);  
vector <ll> ans(maxn);  
vector <bool> isquery(maxn);  
  
void dfs(int node, int a, int b, int h)  
{  
      if (a > b) return;  
      cht[h] = new CHT();  
      for (pll p : Tree[node]) (*cht[h]).add(p.first, p.second);  
      if (a == b)  
      {  
            if (isquery[a] == 0) return;  
            ll maxi = is_query;  
            for (int i = 0; i <= h; i++)  
            {  
                  if ((*cht[i]).size() == 0) continue;  
                  ll dp = (*cht[i]).query(qval[a]);  
                  maxi = max(maxi, dp);  
                  valid[a] = 1;  
            }  
            ans[a] = maxi;  
      }  
      else  
      {  
            int lchild = node * 2;  
            int rchild = lchild + 1;  
            int mid = (a + b) / 2;  
            dfs(lchild, a, mid, h + 1);  
            dfs(rchild, mid + 1, b, h + 1);  
      }  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int n;  
      cin >> n;  
      map <pll, int> in;  
      vector <pll> all_queries(n + 1);  
      for (int i = 1; i <= n; i++)  
      {  
            int type;  
            cin >> type;  
            if (type == 1)  
            {  
                  ll a, b;  
                  cin >> a >> b;  
                  in[mk(a, b)] = i;  
                  all_queries[i] = mk(a, b);  
            }  
            else if (type == 2)  
            {  
                  int id;  
                  cin >> id;  
                  ll a = all_queries[id].first;  
                  ll b = all_queries[id].second;  
                  int l = in[mk(a, b)];  
                  int r = i - 1;  
                  update(1, 1, n, l, r, mk(a, b));  
                  in.erase(mk(a, b));  
            }  
            else  
            {  
                  ll val;  
                  cin >> val;  
                  qval[i] = val;  
                  isquery[i] = 1;  
            }  
      }  
      for (auto it : in)  
      {  
            int l = it.second;  
            int r = n;  
            ll a = it.first.first;  
            ll b = it.first.second;  
            update(1, 1, n, l, r, mk(a, b));  
      }  
      dfs(1, 1, n, 0);  
      for (int i = 1; i <= n; i++)  
      {  
            if (isquery[i] == 0) continue;  
            if (valid[i]) cout << ans[i] << '\n';  
            else cout << "EMPTY SET" << '\n';  
      }  
}