POJ2201 Cartesian Tree (cartesian tree)

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define R(a,b,c) for(register int  a = (b); a <= (c); ++ a)

#define nR(a,b,c) for(register int  a = (b); a >= (c); -- a)

#define Max(a,b) ((a) > (b) ? (a) : (b))

#define Min(a,b) ((a) < (b) ? (a) : (b))

#define Fill(a,b) memset(a, b, sizeof(a))

#define Swap(a,b) a^=b^=a^=b

#define ll long long

#define ON_DEBUG

#ifdef ON_DEBUG

#define D_e_Line printf("\n\n----------\n\n")

#define	D_e(x)	cout << #x << " = " << x << endl

#else

#define D_e_Line ;

#endif

struct ios{

    template<typename ATP>ios& operator >> (ATP &x){

        x = 0; int f = 1; char c;

        for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-')  f = -1;

        while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();

        x*= f;

        return *this;

    }

}io;

using namespace std; 

const int N = 50007;

struct node{

	int l,r,fa,id;

	int val,pri;

	bool operator < (const node &com)const{

		return val < com.val;

	}

}t[N],ans[N];

inline void Insert(int rt){

	int tmp;

	for(tmp = rt - 1; t[tmp].pri > t[rt].pri; tmp = t[tmp].fa);

	t[rt].l = t[tmp].r;

	t[t[tmp].r].fa = rt;

	t[rt].fa = tmp;

	t[tmp].r = rt;

}

int vis[30007];

int main(){

    int n;

    while(scanf("%d", &n) != EOF){

        Fill(vis, false);

        int flag = true;

	    R(i,0,n){

	        t[i].l = t[i].r = t[i].fa = 0;

	        t[i].w = -0x7fffffff;

	    }

        R(i,1,n){

            scanf("%d%d", &t[i].val, &t[i].w);

            t[i].id = i;

            if(vis[t[i].val])

                flag = false;

            else

                vis[t[i].val] = true;

        }

        if(!flag){

        	printf("NO\n");

        	continue;

        }

        printf("YES\n");

		sort(t + 1, t + n + 1);

        R(i,1,n) Insert(i);

        R(i,1,n){

            if(!t[i].l)

                ans[t[i].id].l = 0;

            else

                ans[t[i].id].l = t[t[i].l].id;

            if(!t[i].r)

                ans[t[i].id].r = 0;

            else

                ans[t[i].id].r = t[t[i].r].id;

            if(!t[i].fa)

                ans[t[i].id].fa = 0;

            else

                ans[t[i].id].fa = t[t[i].fa].id;

        }

        R(i,1,n)

            printf("%d %d %d\n", ans[i].fa, ans[i].l, ans[i].r);

    }

    return 0;

}
巴特西

POJ2201 Cartesian Tree (cartesian tree)

最新文章

热门文章
