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 |
Re:求测试数据,WA到死。。。(付线段树代码)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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator