记录编号	266332	评测结果	WWWWTAAAAWAWWAAAAWWAA
题目名称	[HAOI 2014]贴海报	最终得分	52
用户昵称	ConanQZ	是否通过	未通过
代码语言	Pascal	运行时间	1.015 s
提交时间	2016-06-06 21:33:18	内存使用	0.22 MiB

program P2014two;
var
ans,n,i,x,m,tot,k:longint;
l,r:array[1..1010]of longint;
b:array[1..10010]of longint;
w:array[1..2010]of longint;
lb,rb:array[1..2010]of boolean;
p:boolean;

procedure swap(var x,y:longint);
var
z:longint;
begin
z:=x;
x:=y;
y:=z;
end;

procedure sort(l,r:longint);
var
i,j,mid:longint;
begin
i:=l; j:=r;
mid:=w[(l+r)div 2];
repeat
while w[i]<mid do inc(i);
while w[j]>mid do dec(j);
if i<=j then
  begin
   swap(w[i],w[j]);
   inc(i); dec(j);
  end;
until i>j;
if i<r then sort(i,r);
if j>l then sort(l,j);
end;

procedure reduce;
var
i:longint;
begin
k:=1;
for i:=2 to tot do
  if w[i]<>w[k] then
    begin
     inc(k);
     w[k]:=w[i];
    end;
end;

function find(x:longint):longint;
var
l,r:longint;
mid:longint;
begin
l:=1; r:=k;
while l<=r do
  begin
   mid:=(l+r)div 2;
   if x<w[mid] then r:=mid-1
   else if x>w[mid] then l:=mid+1
   else exit(mid);
  end;
end;

begin
//assign(input,'11.in'); reset(input);
//assign(output,'11.out'); rewrite(output);
assign(input,'ha14d.in'); reset(input);
assign(output,'ha14d.out'); rewrite(output);
readln(n,m);
for i:=1 to m do
  begin
   readln(l[i],r[i]);
   inc(tot);w[tot]:=l[i];
   inc(r[i]);inc(tot);w[tot]:=r[i];
  end;
//for i:=1 to m do write(l[i],' '); writeln;
//for i:=1 to m do write(r[i],' '); writeln;

sort(1,tot);
reduce;

for i:=1 to m do
  begin
   l[i]:=find(l[i]);
   r[i]:=find(r[i]);
  end;
//writeln;
//for i:=1 to m do write(l[i],' '); writeln;
//for i:=1 to m do write(r[i],' '); writeln;

for i:=m downto 1 do
  begin
   x:=l[i];
   p:=false;
   while x<=r[i] do
     begin
      if lb[x] then
        begin
         x:=b[x];
         continue;
        end;
      if (rb[x])and(x<r[i]) then
        begin
         if x=l[i] then lb[x]:=true;
         if not p then begin inc(ans); p:=true; {writeln(i)}; end;
         inc(x);
        end
      else if (rb[x])and(x=r[i]) then break;
      if x=r[i] then rb[x]:=true;
      if b[x]=0 then
        begin
         b[x]:=r[i];
         inc(x);
         if x=l[i] then lb[x]:=true;
         if not p then begin inc(ans); p:=true; {writeln(i);} end;
        end else x:=b[x];
     end;
  end;
//for i:=1 to 15 do write(b[i],' ');
writeln(ans);
end.