Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 表示POJ数据是错的 不处理特殊情况 内附反例数据和代码

Posted by _lxy at 2012-04-26 21:58:25 on Problem 2528
```如果你AC了 这组数据必然过不了
1
3
1 10
1 3
6 10

== 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
for tt := 1 to t do
begin
fillchar(c,sizeof(c),0) ;
fillchar(v,sizeof(v),0);
cnt := 0 ;
for i := 1 to n do
begin
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: