| ||||||||||
| 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