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