(Время: 2 сек. Память: 16 Мб Сложность: 62%)
Дано N отрезков на числовой прямой и M точек на этой же прямой. Для каждой из данных точек определите, скольким отрезкам она принадлежит. Точка x считается принадлежащей отрезку с концами a и b, если выполняется двойное неравенство min(a, b) <= x <= max(a, b).
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа N – число отрезков и M – число точек (1 <= N, M <= 10^5). В следующих N строках по два целых числа ai и bi – координаты концов соответствующего отрезка. В последней строке M целых чисел – координаты точек. Все числа во входном файле не превосходят по модулю 10^9.
Выходные данные
В выходной файл OUTPUT.TXT выведите M чисел – для каждой точки количество отрезков, в которых она содержится.
ПРИМЕРЫ
3 2
0 5
-3 2
7 10
1 6
ответ 2 0
1 3
-10 10
-100 100 0
ответ 0 0 1
Моя идея проста: сначала сортируем точки по координате, затем точки с одинаковой координатой сортируем по типу
К сожалению, этот вариант не проходит автоматическую систему проверки по времени (~+0,5сек)
Самого теста у меня нет
Вероятно, надо прикрутить упорядочивание по типу точки в процедуру сортировки по координате, но я не представляю, как это сделать...
А может ещё какой-то вариант есть?
Времени у меня как всегда впритык
program Project1;
type
tip=(_left,_none,_right);
point=record x,n,c:longint; t:tip end;
mas=array [1..300000]of point;
var
a,b:mas;
f:text;
i,n,m,k,j:longint;
t:point;
procedure quicksort(var a: mas; Lo,Hi: integer);
procedure sort(l,r: integer);
var
i,j: integer;
x,y:point;
begin
i:=l; j:=r; x := a[(r+l) div 2];
repeat
while a[i].x<x.x do i:=i+1;
while x.x<a[j].x do j:=j-1;
if i<=j then
begin
if a[i].x > a[j].x then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y
end;
i:=i+1; j:=j-1
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r)
end;
begin
sort(Lo,Hi)
end;
procedure Tquicksort(var a: mas; Lo,Hi: integer);
procedure sort(l,r: integer);
var
i,j: integer;
x,y:point;
begin
i:=l; j:=r; x := a[(r+l) div 2];
repeat
while a[i].t<x.t do i:=i+1;
while x.t<a[j].t do j:=j-1;
if i<=j then
begin
if a[i].t > a[j].t then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y
end;
i:=i+1; j:=j-1
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r)
end;
begin
sort(Lo,Hi)
end;
begin
assign(f,'input.txt');
reset(f);
readln(f,n,m);
k:=1;
for I := 1 to n do {читаем отрезки}
begin
readln(f,a[k].x,a[k+1].x);
a[k].t:=_left; a[k+1].t:=_right;
inc(k,2)
end;
for I := 1 to m do {читаем точки}
begin
read(f,a[k].x);
a[k].t:=_none;
a[k].n:=i;
inc(k)
end;
close(f);
quicksort(a,1,k-1); {сортируем все точки по координате}
for i := 1 to k - 2 do
if a[i].x=a[i+1].x then {находим последовательность точек с одинаковой координатой...}
begin
j:=i+1;
while a[i].x=a[j].x do
inc(j);
tquicksort(a,i,j-1) {...и сортируем её по типу: сначала должны идти _left, затем _none, затем _right}
end;
j:=0;
for I := 1 to k-1 do {считаем количество вхождений точки в отрезки}
case a[i].t of
_none:begin a[i].c:=j; b[a[i].n]:=a[i] end;
_left:inc(j);
_right:dec(j)
end;
assign(f,'output.txt');
rewrite(f);
for i := 1 to m do
if b[i].n>0 then write(f,b[i].c,' ');
close(f)
end.
Заранее спасибо
Была вот такая идея: