比赛 |
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.