萌新再次求救\(&;▔□▔)/
查看原帖
萌新再次求救\(&;▔□▔)/
77760
arfa楼主2018/8/26 15:41

样例都错了(我太弱了)

样例输出:

3
1
3
0
1
0
1
0
0
1

我的输出:

3
1
3
0
0
2
0
0
0
1

帮忙纠错者,无限感激

var
	n,k,i:longint;
	point:array[1..3,-1..1000] of longint;
	num,element:array[-1..1000] of longint;
	value,ans,tree:array[-1..1000] of longint;

procedure swap(var a,b:longint);
var
    t:longint;
begin
	t:=a;
	a:=b;
	b:=t;
end;

procedure Sort_1(l,r:longint);
var
	i,j,s,t:longint;
begin
	i:=l; j:=r; s:=(l+r) div 2;
    repeat
        while (point[1,i]<point[1,s])or((point[1,i]=point[1,s])and(point[2,i]<point[2,s]))or((point[1,i]=point[1,s])and(point[2,i]=point[2,s])and(point[3,i]<point[3,s])) do inc(i);
        while (point[1,j]>point[1,s])or((point[1,j]=point[1,s])and(point[2,j]>point[2,s]))or((point[1,j]=point[1,s])and(point[2,j]=point[2,s])and(point[3,j]>point[3,s])) do dec(j);
        if i<=j then
        begin
        	swap(point[1,i],point[1,j]);
        	swap(point[2,i],point[2,j]);
        	swap(point[3,i],point[3,j]);
		    inc(i); dec(j);
        end;
    until i>=j;
    if i<r then Sort_1(i,r);
    if j>l then Sort_1(l,j);
end;

procedure Sort_2(l,r:longint);
var
	i,j,s,t:longint;
begin
	i:=l; j:=r; s:=(l+r) div 2;
    repeat
        while (element[i]<element[s])or((element[i]=element[s])and(num[i]<num[s])) do inc(i);
        while (element[j]>element[s])or((element[j]=element[s])and(num[j]>num[s])) do dec(j);
        if i<=j then
        begin
        	swap(element[i],element[j]);
        	swap(num[i],num[j]);
		    inc(i); dec(j);
        end;
    until i>=j;
    if i<r then Sort_2(i,r);
    if j>l then Sort_2(l,j);
end;

function lowbit(num:longint):longint; begin exit(num and -num); end;

procedure Insert(x,add:longint);
begin
	while x<=k do
	begin
		inc(tree[x],add);
		inc(x,lowbit(x));
	end;
end;

function Query(x:longint):longint;
begin
	Query:=0;
	while x>0 do
	begin
		inc(Query,tree[x]);
		dec(x,lowbit(x));
	end;
end;

procedure CDQ(l,r:longint);
var
	mid,i,j:longint;
begin
	if l=r then exit;
	mid:=(l+r) div 2;
	CDQ(l,mid);

	for i:=l to r do
	begin
		element[i]:=point[2,i];
		num[i]:=i;
	end;
	Sort_2(l,r);

	for i:=l to r do
		if num[i]<=mid then
			Insert(point[3,num[i]],1)
		else
			inc(value[num[i]],Query(point[3,num[i]]));
	for i:=l to r do
		if num[i]<=mid then
			Insert(point[3,num[i]],-1);
	CDQ(mid+1,r);
end;

begin
	read(n,k);
	for i:=1 to n do
		read(point[1,i],point[2,i],point[3,i]);
	Sort_1(1,n);
	CDQ(1,n);

	for i:=n-1 downto 1 do
		if (point[1,i]=point[1,i+1])and(point[2,i]=point[2,i+1])and(point[3,i]=point[3,i+1]) then
			value[i]:=value[i+1];
	for i:=1 to n do
		inc(ans[value[i]]);
	for i:=0 to n-1 do
		writeln(ans[i]);
end.
2018/8/26 15:41
加载中...