[Gym] Problem G - Galactic Collegiate Programming Contest

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Problem G - Galactic Collegiate Programming Contest
                    Nordic Collegiate Programming Contest 2017
Source            : Gym
Category          : Data Structure
Algorithm         : Policy Based Data Structure
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
static const int maxn = 1e5 + 5;
 
struct node
{
    int id, solved, penalty;
    node(int id = 0, int solved = 0, int penalty = 0)
    {
        this->id = id;
        this->solved = solved;
        this->penalty = penalty;
    }
    friend bool operator < (node a, node b)
    {
        if (a.solved == b.solved)
        {
            if(a.penalty == b.penalty)
            {
                return a.id < b.id;
            }
            return a.penalty < b.penalty;
        }
        return a.solved > b.solved;
    }
};
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
 
template <typename T> using orderset = tree <T,
                                             null_type,
                                             less<T>,
                                             rb_tree_tag,
                                             tree_order_statistics_node_update>;
 
 
 
 
int n, m;
orderset <node> X;
int sol[maxn], pen[maxn];
 
int main()
{
    // freopen("in.txt", "r", stdin);
 
    cin >> n >> m;
    int id = 1;
    for (int i = 1; i <= n; i++)
    {
        X.insert(node(i, 0, 0));
        sol[i] = 0;
        pen[i] = 0;
    }
    for (int i = 0; i < m; i++)
    {
        int t, p;
        cin >> t >> p;
        auto it = X.lower_bound(node(t, sol[t], pen[t]));
        X.erase(it);
        sol[t]++;
        pen[t] += p;
        X.insert(node(t, sol[t], pen[t]));
        int pos = X.order_of_key(node(1, sol[1], pen[1]));
        cout << pos+1 << endl;
    }
}