比赛 20120712 评测结果 AAATTTTTTA
题目名称 区间权最大 最终得分 40
用户昵称 isabella 运行时间 6.007 s
代码语言 Pascal 内存使用 2.93 MiB
提交时间 2012-07-12 11:09:29
显示代码纯文本
type
 point=^node;
 node=record
  d1,d2,id:longint;
  next:point;
  end;
var
 n,m,i,j,temp,mid,x,y:longint;
 a,b,c,ans,aa,bb,cc:array[0..100010]of longint;
 v:array[0..100010]of boolean;
 h,p,f:point;

procedure sort(l,ll:longint);
 var i,j:longint;
 begin
  i:=l;j:=ll;
  mid:=c[(i+j)div 2];
  repeat
   while c[i]<mid do inc(i);
   while c[j]>mid do dec(j);
   if i<=j then
    begin
     temp:=c[i];c[i]:=c[j];c[j]:=temp;
     temp:=a[i];a[i]:=a[j];a[j]:=temp;
     temp:=b[i];b[i]:=b[j];b[j]:=temp;
     inc(i);dec(j);
    end;
  until i>j;
  if i<ll then sort(i,ll);
  if l<j then sort(l,j);
 end;

procedure sort2(l,ll:longint);
 var i,j:longint;
 begin
  i:=l;j:=ll;
  mid:=(i+j)div 2;
  repeat
   while(aa[i]<aa[mid])or((aa[i]=aa[mid])and(bb[i]<bb[mid]))do inc(i);
   while(aa[j]>aa[mid])or((aa[j]=aa[mid])and(bb[j]>bb[mid]))do dec(j);
   if i<=j then
    begin
     temp:=cc[i];cc[i]:=cc[j];cc[j]:=temp;
     temp:=aa[i];aa[i]:=aa[j];aa[j]:=temp;
     temp:=bb[i];bb[i]:=bb[j];bb[j]:=temp;
     inc(i);dec(j);
    end;
  until i>j;
  if i<ll then sort(i,ll);
  if l<j then sort(l,j);
 end;
procedure make;
 var i,j:longint;
 begin
  fillchar(v,sizeof(v),0);
  aa:=a;bb:=b;cc:=c;
  sort2(1,n);
  i:=1;j:=2;
  while j<=n do
   begin
     while (aa[j]=aa[i])and(j<=n) do
      begin
       if(cc[i]>=cc[j])then v[j]:=true;
       inc(j);
      end;
     i:=j;j:=i+1;
   end;
 end;

begin
assign(input,'max.in');reset(input);
assign(output,'max.out');rewrite(output);
 readln(n,m);
 for i:=1 to n do read(a[i],b[i],c[i]);
 sort(1,n);
 for i:=1 to m do
  begin
   read(x,y);
   new(p);p^.d1:=x;p^.d2:=y;p^.id:=i;
   p^.next:=h;h:=p;
  end;

 make;
 for i:=n downto 1 do
 if v[i]=false then
  begin
   p:=h;f:=nil;

   while p<>nil do
    begin
      if (a[i]>=p^.d1)and(b[i]<=p^.d2)then
       begin
         ans[p^.id]:=c[i];
         if f=nil then begin p:=p^.next;h:=p;end
          else begin f^.next:=p^.next;p:=f^.next;end;
       end else
      begin f:=p;p:=p^.next;end;
    end;

  end;

 for i:=1 to m do writeln(ans[i]);
close(input);close(output);
end.