Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

为什么我写的Treap超时,哪个大牛帮我看一下,提点建议。Orz

Posted by kesongyu at 2011-12-16 19:01:52 on Problem 2828
#include <iostream>
#include <cstdio>
#include <ctime>

using namespace std;

struct TreapNode
{
	int value;
	int size;
	int fix;
	TreapNode *left, *right;
	inline int LeftSize()
	{
		return left ? left->size : 0;
	}
	inline int RightSize()
	{
		return right ? right->size : 0;
	}
};

TreapNode *root = NULL;

inline void TreapLeftRotate(TreapNode *&root)
{
	TreapNode *t = root->right;
	root->right = t->left;
	t->left = root;
	root = t;
	root->left->size = root->left->LeftSize() + root->left->RightSize() + 1;
	root->size = root->LeftSize() + root->RightSize() + 1;
}

inline void TreapRightRotate(TreapNode *&root)
{
	TreapNode *t = root->left;
	root->left = t->right;
	t->right = root;
	root = t;
	root->right->size = root->right->LeftSize() + root->right->RightSize() + 1;
	root->size = root->LeftSize() + root->RightSize() + 1;
}

void TreapInsert(TreapNode *&root, int p, int value)
{
	if (!root)
	{
		root = new TreapNode;
		root->left = NULL;
		root->right = NULL;
		root->fix = rand();
		root->size = 1;
		root->value = value;
		return ;
	}
	if (p < root->LeftSize() + 1)
	{
		TreapInsert(root->left, p, value);
		root->size = root->LeftSize() + root->RightSize() + 1;
		if (root->left->fix < root->fix)
		{
			TreapRightRotate(root);
		}
	}
	else
	{
		TreapInsert(root->right, p - root->LeftSize() - 1, value);
		root->size = root->LeftSize() + root->RightSize() + 1;
		if (root->right->fix < root->fix)
		{
			TreapLeftRotate(root);
		}
	}
}

void PrintTreap(TreapNode *&root)
{
	if (root->left)
	{
		PrintTreap(root->left);
		printf(" ");
	}
	printf("%d", root->value);
	if (root->right)
	{
		printf(" ");
		PrintTreap(root->right);
	}
	delete root;
	root = NULL;
}

int main()
{
	freopen("POJ2828.in", "r", stdin);
	freopen("POJ2828.out", "w", stdout);
	int n;
	while (scanf("%d", &n) != EOF)
	{
		srand((unsigned)time(NULL));
		for (int i = 1; i <= n; i++)
		{
			int p, value;
			scanf("%d%d", &p, &value);
			if (root && p > root->size)
			{
				TreapInsert(root, root->size, value);
			}
			else
			{
				TreapInsert(root, p, value);
			}
		}
		PrintTreap(root);
		printf("\n");
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator