比赛 20120712 评测结果 AAATTTTTTA
题目名称 区间权最大 最终得分 40
用户昵称 zhangchi 运行时间 6.001 s
代码语言 Pascal 内存使用 2.83 MiB
提交时间 2012-07-12 11:48:17
显示代码纯文本
var
  n,m,i,j:longint;
  a,b,c,d,e,f,g:array[1..100000] of longint;
  procedure sort1(l,r:longint);
  var
    i,j,t,m:longint;
  begin
    i:=l; j:=r;
    m:=b[(l+r) div 2];
    repeat
      while b[i]<m do inc(i);
      while b[j]>m do dec(j);
      if i<=j then
        begin
          t:=a[i]; a[i]:=a[j]; a[j]:=t;
          t:=b[i]; b[i]:=b[j]; b[j]:=t;
          t:=c[i]; c[i]:=c[j]; c[j]:=t;
          inc(i); dec(j);
        end;
    until i>j;
    if l<j then sort1(l,j);
    if i<r then sort1(i,r);
  end;
  procedure sort2(l,r:longint);
  var
    i,j,t,m1,m2:longint;
  begin
    i:=l; j:=r;
    m1:=d[(l+r) div 2];
    m2:=e[(l+r) div 2];
    repeat
      while (d[i]<m1)or((d[i]=m1)and(e[i]<m2)) do inc(i);
      while (d[j]>m1)or((d[j]=m1)and(e[j]>m2)) do dec(j);
      if i<=j then
        begin
          t:=d[i]; d[i]:=d[j]; d[j]:=t;
          t:=e[i]; e[i]:=e[j]; e[j]:=t;
          t:=f[i]; f[i]:=f[j]; f[j]:=t;
          inc(i); dec(j);
        end;
    until i>j;
    if l<j then sort2(l,j);
    if i<r then sort2(i,r);
  end;
begin
  assign(input,'max.in'); reset(input);
  assign(output,'max.out'); rewrite(output);
  readln(n,m);
  for i:=1 to n do
    readln(a[i],b[i],c[i]);
  sort1(1,n);
  for i:=1 to m do
    begin
      readln(d[i],e[i]);
      f[i]:=i;
    end;
  sort2(1,m);
  i:=1;
  while i<=m do
    begin
      j:=1;
      while d[i]=d[i+1] do
        begin
          while (j<=n)and(b[j]<=e[i]) do
            begin
              if (a[j]>=d[i])and(c[j]>g[f[i]]) then
                g[f[i]]:=c[j];
              inc(j);
            end;
          g[f[i+1]]:=g[f[i]];
          inc(i);
        end;
      while (j<=n)and(b[j]<=e[i]) do
        begin
          if (a[j]>=d[i])and(c[j]>g[f[i]]) then
            g[f[i]]:=c[j];
          inc(j);
        end;
      inc(i);
    end;
  for i:=1 to m do
    writeln(g[i]);
  close(input); close(output);
end.