[CS Academy] Rectangle Fit

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Rectangle Fit
Source            : CS Academy
Category          : Data Structure, PBDS
Algorithm         : Easy implementation of Compressed 2D Binary Indexed Tree for grid of 
                    binary numbers
Verdict           : Accepted

Algo Link : Compressed 2D Binary Indexed Tree

#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;
 
#define pii           pair <int, int>
#define piii          pair <pii, int>
#define mk            make_pair
 
template <typename T> using orderset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
 
static const int maxn = 1e6 + 5;
 
int N = 1000000;
orderset <piii> bit[maxn];
int ptr;
 
void Insert(int x, int y)
{
      for (int i = x; i <= N; i += (i & -i))
      {
            bit[i].insert(mk(mk(y, x), ++ptr));
      }
}
 
void Remove(int x, int y)
{
      for (int i = x; i <= N; i += (i & -i))
      {
            bit[i].erase(mk(mk(y, x), -1));
      }
}
 
int query(int x, int y)
{
      int ans = 0;
      for (int i = x; i > 0; i -= (i & -i))
      {
            ans += bit[i].order_of_key(mk(mk(y + 1, 0), -1));
      }
      return ans;
}
 
signed main()
{
      int n, area;
      scanf("%d %d", &n, &area);
      vector <pii> point;
      for (int i = 1; i <= n; i++)
      {
            int x, y;
            scanf("%d %d", &x, &y);
            point.push_back(mk(x, y));
      }
      sort(point.begin(), point.end());
      for (pii p : point) Insert(p.first, p.second);
      int maxPoints = 0;
      for (int i = 0; i < n; i++)
      {
            int x = point[i].first;
            int y = min(area / x, N);
            int points = query(x, y);
            maxPoints = max(maxPoints, points);
      }
      printf("%d\n", maxPoints);
}