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

菜鸟求助大神,不知我这么离散化对不对?

Posted by pythonboy at 2013-04-29 13:41:01 on Problem 2528
如果题目输入
2
3
1 10
1 4
6 10

3
1 10
1 4
5 10

我离散化后变成
1 7
1 3
5 7

1 6
1 3
4 6
对吗?
为什么一直wa呢?是我的离散化有问题吗?

附代码:求大神指点

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
#define mid ( l + r ) >> 1
#define maxn 20000

struct line
{
    int x;
    int coor;
    int old;
};

bool hash[maxn];
line p[maxn<<2];
int sum[maxn<<4];
int res;

int cmp( line a, line b )
{
    return a.coor < b.coor;
}

int cmp1( line a, line b )
{
    if( a.x != b.x )
    {
        return a.x < b.x;
    }
    return a.coor < b.coor;
}

void pushDown( int rt )
{
    if( sum[rt] )
    {
        sum[rt<<1] = sum[rt<<1|1] = sum[rt];
        sum[rt] = 0;
    }
}

void add( int L, int R, int val, int l, int r, int rt )
{
    if( L<=l && R>=r )
    {
        sum[rt] = val;
        return ;
    }
    if( sum[rt] )
    {
        pushDown( rt );
    }

    int m = mid;
    if( R <= m )
    {
        add( L, R, val, lson );
    }
    else if( L > m )
    {
        add( L, R, val, rson );
    }
    else
    {
        add( L, R, val, lson );
        add( L, R, val, rson );
    }
}

void cal( int l, int r, int rt )
{
    if( l == r )
    {
        //printf("%d ", sum[rt]);
        if( !hash[sum[rt]] && sum[rt] )
        {
            res++;
            hash[sum[rt]]=true;
        }
        return ;
    }

    if( sum[rt] )
    {
        pushDown(rt);
    }

    int m = mid;
    cal( lson );
    cal( rson );
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        for( int i=0; i<n; i++ )
        {
            scanf("%d %d", &p[i<<1].coor, &p[i<<1|1].coor);
            p[i<<1].old = p[i<<1].coor;
            p[i<<1|1].old = p[i<<1|1].coor;
            p[i<<1].x = p[i<<1|1].x = i+1;
        }

        sort( p, p+2*n, cmp );

        //li san hua
        p[0].coor = 1;
        for( int i=1; i<2*n-1; i++ )
        {
            if( p[i].old == p[i+1].old )
            {
                p[i+1].coor = p[i].coor;

            }
            else if( p[i].old+1 != p[i+1].old )
            {
               p[i+1].coor = p[i].coor + 2;
            }
            else
            {
                p[i+1].coor = p[i].coor + 1;
            }
        }

        int N = p[2*n-2].coor;
        sort( p, p+2*n, cmp1 );

        memset( hash, false, sizeof( hash ) );
        memset( sum, 0, sizeof( sum ) );

        for( int i=0; i<n; i++ )
        {
            add( p[i<<1].coor, p[i<<1|1].coor, i+1, 1, N, 1 );
        }

        res = 0;
        cal( 1, N, 1 );
        //puts("");
        printf("%d\n", res);

    }

    return 0;
}

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