Cartesian tree, insert sorted

#include<bits/stdc++.h>
using namespace std;

const int MAX_CNT = 50001;

struct Node
{
  int key, y;
  int left, right, parent;
  Node(int x = 0): key(x), y(0), left(0), right(0), parent(0) {}
};

Node nodes[MAX_CNT + 1];

int root_id = 0; // id of root node

int insert_sorted(const int & right_node, const int & key, const int & y, const int & new_node)
{
  int parent_node = right_node, left_node = 0;
  while (parent_node != 0 && nodes[parent_node].y > y)
  {
    left_node = parent_node;
    parent_node = nodes[parent_node].parent;
  }
  nodes[new_node].key = key;
  nodes[new_node].y = y;
  nodes[new_node].parent = parent_node;
  nodes[new_node].left = left_node;
  if ( left_node != 0 ) nodes[left_node].parent = new_node;
  if ( parent_node != 0 ) nodes[parent_node].right = new_node;
  return new_node;
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // freopen("INPUT.TXT", "r", stdin);
  int n;
  cin >> n;
  vector< tuple<int,int,int> > data;
  for(int i=0; i<n; ++i)
  {
    int a, b;
    cin >> a >> b;
    data.push_back( tuple<int,int,int>(a, b, i+1) );
  }
  sort(data.begin(), data.end());

  int right_node = root_id;
  for(auto & e: data)
  {
    int x, y, i;
    tie(x, y, i) = e;
    right_node = insert_sorted(right_node, x, y, i);
  }
  cout << "YES" << endl;
  for(int i=1; i <= n; ++i)
  {
    cout << nodes[i].parent << " " << nodes[i].left << " " << nodes[i].right << endl;
  }
}