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

求大神解答为什么我的代码unsigned intAC,longlong WA?附代码

Posted by 1120121860 at 2013-08-31 18:25:23 on Problem 3832
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#define INF 9999999

using namespace std;

struct Seg
{
	int l;
	int r;
	int y;
	int v;

	Seg(int L,int R,int Y,int V):l(L),r(R),y(Y),v(V){}
	Seg(){}

	bool operator<(const Seg& s) const 
	{
		if(y != s.y)
			return y < s.y;
		else 
			return v > s.v;
	}

}ss[50050 << 2];

int length[50050 << 2];
int nLayer[50050 << 2];

void calc(int index,int l,int r)
{
	if(nLayer[index])
		length[index] = r - l + 1;
	else if(l == r)
		length[index] = 0;
	else
		length[index] = length[index<<1] + length[index<<1|1];
}

void PullUp(int index,int l,int r)
{
	if(nLayer[index << 1] && nLayer[index << 1|1]){
		int tmp = (nLayer[index<<1] < nLayer[index<<1|1]) ? nLayer[index<<1] : nLayer[index<<1|1];
		nLayer[index] = tmp;
		nLayer[index<<1] -= tmp;
		nLayer[index<<1|1] -= tmp;
		int mid = (l+r) >>1;
		calc(index<<1,l,mid);
		calc(index<<1|1,mid+1,r);
	}
}


void PushDown(int index,int l,int r)
{
	if(nLayer[index])
	{
		nLayer[index<<1] += nLayer[index];
		nLayer[index<<1|1] += nLayer[index];
		int mid = (l + r) >> 1;
		calc(index<<1,l,mid);
		calc(index<<1|1,mid + 1,r);
		nLayer[index] = 0;
		calc(index,l,r);
	}
}

void update(int a,int b,int v,int l,int r,int index)
{
	if(a<=l && r<=b){
		nLayer[index] += v;
		calc(index,l,r);
		return;
	}
	PushDown(index,l,r);
	int mid = (l + r) >> 1;
	if(a <= mid)
		update(a,b,v,l,mid,index<<1);
	if(b > mid)
		update(a,b,v,mid+1,r,index<<1|1);
	PullUp(index,l,r);
	calc(index,l,r);
}

int main()
{

   // freopen("/home/leo/in","r",stdin);
	//freopen("/home/leo/out","w",stdout);
	int N;
	while(scanf("%d",&N) && N){
		int m = 0;
		memset(length,0,sizeof(length));
		memset(nLayer,0,sizeof(nLayer));
		for(int i = 0; i < N; ++i){
			int x1,y1,x2,y2,x3,y3,x4,y4;
			scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
			ss[m++] = Seg(x1,x2,y1,1);
			ss[m++] = Seg(x3,x4,y3,-1);
			ss[m++] = Seg(x3,x4,y4,1);
			ss[m++] = Seg(x1,x2,y2,-1);
		}
		sort(ss,ss + m);
		unsigned int ans = 0;//!!!!!!!!!!!!!!
		for(int i = 0; i < m - 1; ++i)
		{
			update(ss[i].l,ss[i].r - 1,ss[i].v,0,50000,1);
			ans += length[1] * (ss[i+1].y - ss[i].y);
		}
		cout<<ans<<endl;
	}
}

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