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 |
haha , 我也过了这个数据, 也ac了In Reply To:表示POJ数据是错的 不处理特殊情况 内附反例数据和代码 Posted by:_lxy at 2012-04-26 21:58:25 > 如果你AC了 这组数据必然过不了 > 1 > 3 > 1 10 > 1 3 > 6 10 > > 正确是3 但是只当你算出来是2的时候你才能A > 为什么呢 > 因为4-5这段区间离散化的时候并没有处理到 > > 下面是最后的AC程序 加上大括号部分代码之后才是正确程序 > > > > > > > > == Code == > > > > > > program poj2528; > var > c:array[0..80000] of longint; > v:array[0..30000] of longint; > o:array[0..30000] of boolean ; > a,b:array[1..10000] of longint; > t,tt,n,i,x,cnt,ans:longint; > > procedure qsort(l,r:longint) ; > var > i,j,t,x:longint; > begin > i := l; > j := r; > x := v[(l+r) shr 1] ; > repeat > while v[i] < x do inc(i) ; > while v[j] > x do dec(j) ; > if i <= j then > begin > t := v[i] ; > v[i] := v[j] ; > v[j] := t ; > inc(i) ; > dec(j) ; > end; > until i > j ; > if i < r then qsort(i,r) ; > if l < j then qsort(l,j) ; > end; > > procedure pushdown(x:longint); > begin > if c[x] <> 0 then > begin > c[x shl 1] := c[x] ; > c[x shl 1+1] := c[x] ; > c[x] := 0 ; > end; > end; > > procedure modify(ll,rr,u,l,r,x:longint) ; > var > m:longint; > begin > if (ll <= l) and (r <= rr) then > begin > c[x] := u ; > exit ; > end; > pushdown(x) ; > m := (l+r) shr 1; > if ll <= m then modify(ll,rr,u,l,m,x shl 1) ; > if m < rr then modify(ll,rr,u,m+1,r,x shl 1+1) ; > end; > > function query(l,r,x:longint):longint; > var > m:longint; > begin > if l > r then exit; > if c[x] <> 0 then > begin > if not o[c[x]] then > begin > o[c[x]] := true ; > inc(ans) ; > end ; > exit; > end; > if l = r then exit ; > m := (l+r) shr 1; > query(l,m,x shl 1); > query(m+1,r,x shl 1+1); > end; > > function seek(x:longint):longint; > var > l,r,m:longint; > begin > l := 1; > r := cnt ; > while l <= r do > begin > m := (l+r) shr 1 ; > if v[m] = x then exit(m) else > if v[m] < x then > l := m+1 else > r := m-1 ; > end ; > exit(l) ; > end; > > BEGIN > read(t) ; > for tt := 1 to t do > begin > fillchar(c,sizeof(c),0) ; > read(n) ; > fillchar(v,sizeof(v),0); > cnt := 0 ; > for i := 1 to n do > begin > read(a[i],b[i]) ; > inc(cnt) ; > v[cnt] := a[i] ; > inc(cnt) ; > v[cnt] := b[i] ; > end; > qsort(1,cnt) ; > x := 0 ; > for i := 1 to cnt do > if v[i] <> v[i-1] then > begin > inc(x) ; > v[x] := v[i] ; > end; > cnt := x ; { > for i := 2 to cnt do > if v[i]-v[i-1] > 1 then > begin > inc(x) ; > v[x] := v[i-1]+1; > end; > cnt := x ; } > qsort(1,cnt); > for i := 1 to n do > modify(seek(a[i]),seek(b[i]),i,1,cnt,1) ; > fillchar(o,sizeof(o),false) ; > ans := 0 ; > query(1,cnt,1) ; > writeln(ans) ; > end; > END. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator