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
ACM ICPC 2018 World Finals

haha , 我也过了这个数据, 也ac了

Posted by rush_again at 2013-05-24 10:39:37 on Problem 2528
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:
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