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

Re:求测试数据,WA到死。。。(付线段树代码)

Posted by newpoo at 2008-02-29 11:30:45 on Problem 2528
In Reply To:求测试数据,WA到死。。。(付线段树代码) Posted by:newpoo at 2008-02-29 11:24:41
哪位有数据或者找到bug了麻烦发我信箱通知一声,多谢了!

> #include <cstdio>
> #include <algorithm>
> 
> using namespace std;
> 
> int poster_x[10040];
> int poster_y[10040];
> int n;
> int point[40040];
> char flag[10040];
> int tot;
> int begin[80040];
> int end[80040];
> int lc[80040];
> int rc[80040];
> char color[80040];
> char needclear[80040];
> 
> void MakeTree(int x, int y)
> {
> 	++tot;
> 	int v = tot;
> 	begin[v] = point[x];
> 	end[v] = point[y];
> 	color[v] = 0;
> 	needclear[v] = 0;
> 	if(x + 1 == y)
> 	{
> 		lc[v] = 0;
> 		rc[v] = 0;
> 	}
> 	else
> 	{
> 		lc[v] = tot + 1;
> 		MakeTree(x, (x + y) / 2);
> 		rc[v] = tot + 1;
> 		MakeTree((x + y) / 2, y);
> 	}
> }
> 
> void clear(int num)
> {
> 	needclear[num] = 0;
> 	if(lc[num] != 0) // internal node
> 	{
> 		color[lc[num]] = color[num];
> 		color[rc[num]] = color[num];
> 		needclear[lc[num]] = 1;
> 		needclear[rc[num]] = 1;
> 	}
> }
> 
> void Insert(int x, int y, int c, int num)
> {
> 	if(needclear[num])
> 		clear(num);
> 
> 	if(begin[num] >= x && end[num] <= y)
> 	{
> 		color[num] = c;
> 		clear(num);
> 	}
> 	else
> 	{
> 		if(color[num] != c)
> 		{
> 			color[num] = -1;
> 			if(x < end[lc[num]])
> 				Insert(x, y, c, lc[num]);
> 			if(y > begin[rc[num]])
> 				Insert(x, y, c, rc[num]);
> 		}
> 	}
> }
> 
> void Query(int num)
> {
> 	if(needclear[num])
> 		clear(num);
> 	if(color[num] >= 0)
> 		flag[color[num]] = 1;
> 	else
> 	{
> 		Query(lc[num]);
> 		Query(rc[num]);
> 	}
> }
> 
> int main(void)
> {
> 	int c;
> 	scanf("%d", &c);
> 
> 	while(c--)
> 	{
> 		scanf("%d", &n);
> 		for(int i = 0; i < n; ++i)
> 		{
> 			scanf("%d%d", &poster_x[i], &poster_y[i]);
> 			point[2 * i] = --poster_x[i];
> 			point[2 * i + 1] = poster_y[i];
> 		}
> 		sort(point, point + 2 * n);
> 
> 		int pos = 1;
> 		for(int i = 1; i < 2 * n; ++i)
> 		{
> 			if(point[i] != point[pos - 1])
> 				point[pos++] = point[i];
> 		}
> 
> 		tot = 0;
> 		MakeTree(0, pos-1);
> 		for(int i = 0; i < n; ++i)
> 		{
> 			Insert(poster_x[i], poster_y[i], i + 1, 1);
> 		}
> 
> 		memset(flag, 0, sizeof(char) * (n + 1));
> 
> 		Query(1);
> 		int sum = 0;
> 		for(int i = 1; i <= n; ++i)
> 			sum += flag[i];
> 		printf("%d\n", sum);
> 	}
> }

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