Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

总是TLE,LAZY标记都用上了..为什么还是TLE,和AC的代码对比过结果,完全相同呀,不知道哪里出问题了,我崩馈了...哪位好心人可以帮我看看呀??

Posted by fengxue2026 at 2011-06-27 01:17:44 on Problem 3225

#include<stdio.h>
#include<string.h>
#define INT_MAX 2147483647
const int N = 65535 * 2;
const int maxn = N * 4;

int len;
char s[2],str[20],ch1,ch2;
int c,d;


//ans
char LEFT;
char RIGHT;
int LX[N * 10];
int RY[N * 10];
int cnt;
//
/////////////////////
struct node
{
	int a,b;
	char cov; // 0 ,1 but  -1:mix     
};

node tree[maxn];

void maketree(int a,int b,int k)
{
	tree[k].a = a;
	tree[k].b = b;
	tree[k].cov = 0;

	if(a == b)
		return;

	int mid = (a+b)>>1;
	maketree(a,mid,k<<1);
	maketree(mid+1,b,k<<1|1);
}


inline void push_down(int k)
{
	tree[k<<1].cov = tree[k].cov;
	tree[k<<1|1].cov = tree[k].cov;
	tree[k].cov = -1;
}

inline void update_info(int k)   //自底向上,更新父结点的cov值
{
	if(tree[k<<1].cov == tree[k<<1|1].cov)  //颜色相同,合并线段
		tree[k].cov = tree[k<<1].cov;
	else
		tree[k].cov = -1;
}

////////////////////
void insert(int c,int d,int k)    //插入线段c--d
{
	if(tree[k].cov == 1)   //线段已是纯色了,不用再次插入
		return;

	//cov == 0 或 -1
	if(c <= tree[k].a && tree[k].b <= d)   //完全覆盖,则直接改写cov值
	{
		tree[k].cov = 1;
		return;
	}

	if(tree[k].cov == 0)
		push_down(k);
	
	if(c <= tree[k<<1].b)
		insert(c,d,k<<1);

	if(d >= tree[k<<1|1].a)
		insert(c,d,k<<1|1);

	update_info(k);   //自底向上,更新父结点的cov值
}


////////////////////////////
void del(int c,int d,int k)    //删除线段c--d
{
	if(tree[k].cov == 0)   //线段是空的,不用再次删除
		return;

	//cov == 1 或 -1
	if(c <= tree[k].a && tree[k].b <= d)  //完全覆盖,则直接删除
	{
		tree[k].cov = 0;
		return;
	}

	if(tree[k].cov == 1)
		push_down(k);
	
	if(c <= tree[k<<1].b)
		del(c,d,k<<1);

	if(d >= tree[k<<1|1].a)
		del(c,d,k<<1|1);

	update_info(k);   //自底向上,更新父结点的cov值
}


/////////////////////////////////////////
void insert_xor(int c,int d,int k)    //异或地插入线段[c,d]: 遇到空的线段,直接插入..遇到纯色的线段,删除纯色...
{
	if(tree[k].cov == 1)   //遇到纯色的线段,删除纯色.
	{
		tree[k].cov = 0;
		return;
	}

	//cov == 0 或 -1
	if(c <= tree[k].a && tree[k].b <= d && tree[k].cov == 0)  //遇到空的线段,直接插入
	{
		tree[k].cov = 1;
		return;
	}

	if(tree[k].cov == 0)
		push_down(k);
	
	if(c <= tree[k<<1].b)
		insert_xor(c,d,k<<1);

	if(d >= tree[k<<1|1].a)
		insert_xor(c,d,k<<1|1);

	update_info(k);   //自底向上,更新父结点的cov值
}


//////////////////////////////////////////////////
void insert_sym(int c,int d,int k)    // //加入区域c,d..遇到相交的部分就去除.保留不相交部分.xor异或,很方便
{

	if(c <= tree[k].a && tree[k].b <= d && tree[k].cov >= 0)  //完全覆盖的话,xor一下..
	{
		tree[k].cov ^= 1;
		return;
	}

	if(tree[k].cov >= 0)
		push_down(k);
	
	if(c <= tree[k<<1].b)
		insert_sym(c,d,k<<1);

	if(d >= tree[k<<1|1].a)
		insert_sym(c,d,k<<1|1);

	update_info(k);   //自底向上,更新父结点的cov值
}
////////////////




inline int str_int(char *str,int i,int j)
{
	int x = 0;
	for(int k = i; k<= j; k++)
	{
		x *= 10;
		x += str[k] - 48;
	}
	return x;
}
inline bool pre()
{
	len = strlen(str);
	ch1 = str[0];
	ch2 = str[len-1];

	int mid = 2;

	while(str[mid] != ',') mid++;

	c = str_int(str,1,mid-1);
	
	d = str_int(str,mid+1,len-2);

	if(c > d)   //空集
		return false;

	if((c==d) && (ch1 == '(' || ch2 == ')')) //空集
		return false;

	if(ch1 == '[')
		c *= 2;
	else
		c = c*2 + 1;

	if(ch2 == ']')
		d *= 2;
	else
		d = d*2 - 1;

	return true;
}


/////////////////////////
int x = -INT_MAX,y = -INT_MAX;


void Query(int k)    //O(N)
{
	if(tree[k].cov == 0)
		return;

	if(tree[k].cov == 1)
	{
		if(y + 1 == tree[k].a) //如果区间可合并,则合并
			y = tree[k].b;
		else
		{
			cnt++;
			LX[cnt] = x;
			RY[cnt] = y;

			x = tree[k].a;
			y = tree[k].b;
		}

		return;
	}

	//cov == -1
	Query(k<<1);
	Query(k<<1|1);
}

///////////

int main()
{
	maketree(0,N,1);

	while(scanf("%s%s",s,str)!=EOF)
	{

		if(pre())
		{
			switch(s[0])
			{
			case 'U':      //并
				insert(c,d,1);
				break;
		
			case 'I':      //交
				del(0,c-1,1);
				del(d+1,N,1);  //交运算,实质是对原线段删除c,d以外的区域,注意不用再插入线段[c,d]
				break;
		
			case 'D':       //差
				del(c,d,1);   //实质是在原有的线段a---b 上删除c--d
				break;
		
			case 'C':       //逆差,实质是对原线段删除c,d以外的区域,然后再xor异或地插入线段[c,d]
				del(0,c-1,1); //
				del(d+1,N,1);  // //除去c,d以外的区域

				insert_xor(c,d,1);   //异或地插入线段[c,d]: 遇到空的线段,直接插入..遇到纯色的线段,删除纯色...
				break;
		
			case 'S':       //对称差
				insert_sym(c,d,1);   //加入区域c,d..遇到相交的部分就去除.保留不相交部分.xor异或,很方便
			}
		}
		else //空集
		{
			switch(s[0])
			{
			case 'U':      //并   并空集 == 原集
				break;
		
			case 'I':      //交
				tree[1].cov = 0; //S 交 空集 == 空集
				break;
		
			case 'D':       //差  差空集 == 原集
				break;
		
			case 'C':       //逆差, 逆差空集 == 空集
				tree[1].cov = 0;
				break;
		
			case 'S':       //对称差 无影响  == 原集
				break;
			}
		}

	}

	cnt = 0;
	Query(1);

	//最后一个区间 
	cnt++;
	LX[cnt] = x;
	RY[cnt] = y;
	

	if(cnt == 1)
		printf("empty set\n");
	else
	for(int i=2; i <= cnt; i++)
	{
		
		printf("%c%d,%d%c", LX[i]&1?'(':'[', LX[i]>>1, (RY[i]+1)>>1, RY[i]&1?')':']');

		if(i == cnt) printf("\n");
		else
			printf(" ");
	}

	//
	return 0;
}

Followed by:

大概看了一下，LZ写的懒标记有点奇怪= = (5740) xuhaoran510 2011-06-27 08:48:11

Post your reply here:

User ID:
Password:
Title:

Content:

> #include<stdio.h>
> #include<string.h>
> #define INT_MAX 2147483647
> const int N = 65535 * 2;
> const int maxn = N * 4;
> 
> int len;
> char s[2],str[20],ch1,ch2;
> int c,d;
> 
> 
> //ans
> char LEFT;
> char RIGHT;
> int LX[N * 10];
> int RY[N * 10];
> int cnt;
> //
> /////////////////////
> struct node
> {
> 	int a,b;
> 	char cov; // 0 ,1 but  -1:mix     
> };
> 
> node tree[maxn];
> 
> void maketree(int a,int b,int k)
> {
> 	tree[k].a = a;
> 	tree[k].b = b;
> 	tree[k].cov = 0;
> 
> 	if(a == b)
> 		return;
> 
> 	int mid = (a+b)>>1;
> 	maketree(a,mid,k<<1);
> 	maketree(mid+1,b,k<<1|1);
> }
> 
> 
> inline void push_down(int k)
> {
> 	tree[k<<1].cov = tree[k].cov;
> 	tree[k<<1|1].cov = tree[k].cov;
> 	tree[k].cov = -1;
> }
> 
> inline void update_info(int k)   //自底向上,更新父结点的cov值
> {
> 	if(tree[k<<1].cov == tree[k<<1|1].cov)  //颜色相同,合并线段
> 		tree[k].cov = tree[k<<1].cov;
> 	else
> 		tree[k].cov = -1;
> }
> 
> ////////////////////
> void insert(int c,int d,int k)    //插入线段c--d
> {
> 	if(tree[k].cov == 1)   //线段已是纯色了,不用再次插入
> 		return;
> 
> 	//cov == 0 或 -1
> 	if(c <= tree[k].a && tree[k].b <= d)   //完全覆盖,则直接改写cov值
> 	{
> 		tree[k].cov = 1;
> 		return;
> 	}
> 
> 	if(tree[k].cov == 0)
> 		push_down(k);
> 	
> 	if(c <= tree[k<<1].b)
> 		insert(c,d,k<<1);
> 
> 	if(d >= tree[k<<1|1].a)
> 		insert(c,d,k<<1|1);
> 
> 	update_info(k);   //自底向上,更新父结点的cov值
> }
> 
> 
> ////////////////////////////
> void del(int c,int d,int k)    //删除线段c--d
> {
> 	if(tree[k].cov == 0)   //线段是空的,不用再次删除
> 		return;
> 
> 	//cov == 1 或 -1
> 	if(c <= tree[k].a && tree[k].b <= d)  //完全覆盖,则直接删除
> 	{
> 		tree[k].cov = 0;
> 		return;
> 	}
> 
> 	if(tree[k].cov == 1)
> 		push_down(k);
> 	
> 	if(c <= tree[k<<1].b)
> 		del(c,d,k<<1);
> 
> 	if(d >= tree[k<<1|1].a)
> 		del(c,d,k<<1|1);
> 
> 	update_info(k);   //自底向上,更新父结点的cov值
> }
> 
> 
> /////////////////////////////////////////
> void insert_xor(int c,int d,int k)    //异或地插入线段[c,d]: 遇到空的线段,直接插入..遇到纯色的线段,删除纯色...
> {
> 	if(tree[k].cov == 1)   //遇到纯色的线段,删除纯色.
> 	{
> 		tree[k].cov = 0;
> 		return;
> 	}
> 
> 	//cov == 0 或 -1
> 	if(c <= tree[k].a && tree[k].b <= d && tree[k].cov == 0)  //遇到空的线段,直接插入
> 	{
> 		tree[k].cov = 1;
> 		return;
> 	}
> 
> 	if(tree[k].cov == 0)
> 		push_down(k);
> 	
> 	if(c <= tree[k<<1].b)
> 		insert_xor(c,d,k<<1);
> 
> 	if(d >= tree[k<<1|1].a)
> 		insert_xor(c,d,k<<1|1);
> 
> 	update_info(k);   //自底向上,更新父结点的cov值
> }
> 
> 
> //////////////////////////////////////////////////
> void insert_sym(int c,int d,int k)    // //加入区域c,d..遇到相交的部分就去除.保留不相交部分.xor异或,很方便
> {
> 
> 	if(c <= tree[k].a && tree[k].b <= d && tree[k].cov >= 0)  //完全覆盖的话,xor一下..
> 	{
> 		tree[k].cov ^= 1;
> 		return;
> 	}
> 
> 	if(tree[k].cov >= 0)
> 		push_down(k);
> 	
> 	if(c <= tree[k<<1].b)
> 		insert_sym(c,d,k<<1);
> 
> 	if(d >= tree[k<<1|1].a)
> 		insert_sym(c,d,k<<1|1);
> 
> 	update_info(k);   //自底向上,更新父结点的cov值
> }
> ////////////////
> 
> 
> 
> 
> inline int str_int(char *str,int i,int j)
> {
> 	int x = 0;
> 	for(int k = i; k<= j; k++)
> 	{
> 		x *= 10;
> 		x += str[k] - 48;
> 	}
> 	return x;
> }
> inline bool pre()
> {
> 	len = strlen(str);
> 	ch1 = str[0];
> 	ch2 = str[len-1];
> 
> 	int mid = 2;
> 
> 	while(str[mid] != ',') mid++;
> 
> 	c = str_int(str,1,mid-1);
> 	
> 	d = str_int(str,mid+1,len-2);
> 
> 	if(c > d)   //空集
> 		return false;
> 
> 	if((c==d) && (ch1 == '(' || ch2 == ')')) //空集
> 		return false;
> 
> 	if(ch1 == '[')
> 		c *= 2;
> 	else
> 		c = c*2 + 1;
> 
> 	if(ch2 == ']')
> 		d *= 2;
> 	else
> 		d = d*2 - 1;
> 
> 	return true;
> }
> 
> 
> /////////////////////////
> int x = -INT_MAX,y = -INT_MAX;
> 
> 
> void Query(int k)    //O(N)
> {
> 	if(tree[k].cov == 0)
> 		return;
> 
> 	if(tree[k].cov == 1)
> 	{
> 		if(y + 1 == tree[k].a) //如果区间可合并,则合并
> 			y = tree[k].b;
> 		else
> 		{
> 			cnt++;
> 			LX[cnt] = x;
> 			RY[cnt] = y;
> 
> 			x = tree[k].a;
> 			y = tree[k].b;
> 		}
> 
> 		return;
> 	}
> 
> 	//cov == -1
> 	Query(k<<1);
> 	Query(k<<1|1);
> }
> 
> ///////////
> 
> int main()
> {
> 	maketree(0,N,1);
> 
> 	while(scanf("%s%s",s,str)!=EOF)
> 	{
> 
> 		if(pre())
> 		{
> 			switch(s[0])
> 			{
> 			case 'U':      //并
> 				insert(c,d,1);
> 				break;
> 		
> 			case 'I':      //交
> 				del(0,c-1,1);
> 				del(d+1,N,1);  //交运算,实质是对原线段删除c,d以外的区域,注意不用再插入线段[c,d]
> 				break;
> 		
> 			case 'D':       //差
> 				del(c,d,1);   //实质是在原有的线段a---b 上删除c--d
> 				break;
> 		
> 			case 'C':       //逆差,实质是对原线段删除c,d以外的区域,然后再xor异或地插入线段[c,d]
> 				del(0,c-1,1); //
> 				del(d+1,N,1);  // //除去c,d以外的区域
> 
> 				insert_xor(c,d,1);   //异或地插入线段[c,d]: 遇到空的线段,直接插入..遇到纯色的线段,删除纯色...
> 				break;
> 		
> 			case 'S':       //对称差
> 				insert_sym(c,d,1);   //加入区域c,d..遇到相交的部分就去除.保留不相交部分.xor异或,很方便
> 			}
> 		}
> 		else //空集
> 		{
> 			switch(s[0])
> 			{
> 			case 'U':      //并   并空集 == 原集
> 				break;
> 		
> 			case 'I':      //交
> 				tree[1].cov = 0; //S 交 空集 == 空集
> 				break;
> 		
> 			case 'D':       //差  差空集 == 原集
> 				break;
> 		
> 			case 'C':       //逆差, 逆差空集 == 空集
> 				tree[1].cov = 0;
> 				break;
> 		
> 			case 'S':       //对称差 无影响  == 原集
> 				break;
> 			}
> 		}
> 
> 	}
> 
> 	cnt = 0;
> 	Query(1);
> 
> 	//最后一个区间 
> 	cnt++;
> 	LX[cnt] = x;
> 	RY[cnt] = y;
> 	
> 
> 	if(cnt == 1)
> 		printf("empty set\n");
> 	else
> 	for(int i=2; i <= cnt; i++)
> 	{
> 		
> 		printf("%c%d,%d%c", LX[i]&1?'(':'[', LX[i]>>1, (RY[i]+1)>>1, RY[i]&1?')':']');
> 
> 		if(i == cnt) printf("\n");
> 		else
> 			printf(" ");
> 	}
> 
> 	//
> 	return 0;
> }

Home Page Go Back To top

总是TLE,LAZY标记都用上了..为什么还是TLE,和AC的代码对比过结果,完全相同呀,不知道哪里 出问题了,我崩馈了...哪位好心人可以帮我看看呀??

总是TLE,LAZY标记都用上了..为什么还是TLE,和AC的代码对比过结果,完全相同呀,不知道哪里出问题了,我崩馈了...哪位好心人可以帮我看看呀??