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 |
求大神解答为什么我的代码unsigned intAC,longlong WA?附代码#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator