solution-code1608

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#include <cmath>
6
using namespace std;
7
struct Node
8
{
9
  int x,y,id;
10
}a[50005];
11
int n,f[50005][17],pos[50005][17],fa[50005],Ls[50005],Rs[50005];
12
inline void Init(void)
13
{
14
  int i,j;
15
  for(i=1;i<=n;++i)
16
  {
17
    f[i][0]=a[i].y;
18
    pos[i][0]=i;
19
  }
20
  for(j=1;j<=16;++j)
21
  {
22
    for(i=1;i+(1<<j)-1<=n;++i)
23
    {
24
      if(f[i][j-1]<f[i+(1<<(j-1))][j-1])
25
      {
26
        f[i][j]=f[i][j-1];
27
        pos[i][j]=pos[i][j-1];
28
      }
29
      else if(f[i][j-1]>f[i+(1<<(j-1))][j-1])
30
      {
31
        f[i][j]=f[i+(1<<(j-1))][j-1];
32
        pos[i][j]=pos[i+(1<<(j-1))][j-1];
33
      }
34
    }
35
  }
36
  return;
37
}
38
inline int Ask(int L,int R)
39
{
40
  int x=log2(R-L+1);
41
  if(f[L][x]<=f[R-(1<<x)+1][x])return pos[L][x];
42
  else return pos[R-(1<<x)+1][x];
43
}
44
inline int dfs(int L,int R,int pre)
45
{
46
  if(L>R)return 0;
47
  int mid=Ask(L,R),x=a[mid].id;
48
  fa[x]=pre;
49
  Ls[x]=dfs(L,mid-1,x);
50
  Rs[x]=dfs(mid+1,R,x);
51
  return x;
52
}
53
inline bool cmp(const Node& a,const Node& b)
54
{
55
  return a.x<b.x;
56
}
57
int main(void)
58
{
59
  int i,x,y,rt;
60
  scanf("%d",&n);
61
  for(i=1;i<=n;++i)
62
  {
63
    scanf("%d%d",&x,&y);
64
    a[i]=(Node){x,y,i};
65
  }
66
  sort(a+1,a+n+1,cmp);
67
  Init();
68
  rt=dfs(1,n,0);
69
  printf("YES\n");
70
  for(i=1;i<=n;++i)printf("%d %d %d\n",fa[i],Ls[i],Rs[i]);
71
  return 0;
72
}