| ||||||||||
| 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 | |||||||||
菜鸟求助大神,不知我这么离散化对不对?如果题目输入
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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator