105 - The Skyline Problem

[tmdrbs6584]

Hi logic
Bye logic

[f.eliel]

I don

[Solaris]

I dont think your code matches the sample input. Just put the main printing FOR loop out of the WHILE loop. Otherwise your code is Ok.

Remove your code after u get AC.

[sds1100]

logic

[sds1100]

i me too imlazy짱깨
sorry.
sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.

[coldfire]

I tested every possible legal test on my computer, but i can't find the bug .. if anyone could help me ... please ...

I use interval trees for better time...

//{$S-,R-,Q-,B-}

const maxN = 6000;
maxL = 30000;

type triple = record
x, h, s: longint;
end;

var d: array[0..maxN] of triple;
x, y, h, n, i, j, max: longint;
a, b: array[0..maxL] of longint;

procedure read_data;
//var f: text;
begin

// assign(f, '105.in'); reset(f);

n := 0;
while not eof(input) do begin

readln(x, h, y);

if x < y then begin
inc(n); d[n].x := x; d[n].h := h; d[n].s := 1;
inc(n); d[n].x := y; d[n].h := h; d[n].s := -1;
end;

end;

// close(f);

end;

procedure qSort(l, r: longint);
var
i, j, x: longint;
y: triple;
begin
i := l; j := r; x := d[(l+r) DIV 2].x;
repeat
while d.x < x do i := i + 1;
while x < d[j].x do j := j - 1;
if i <= j then
begin
y := d; d := d[j]; d[j] := y;
i := i + 1; j := j - 1;
end;
until i > j;
if l < j then qSort(l, j);
if i < r then qSort(i, r);
end;

procedure update(k, l, r, s: longint);
var m: longint;
begin

if (r <= d[j].h) then begin

if s = -1 then begin
dec(a[k]);
if a[k] = 0 then b[k] := b[k * 2] + b[k * 2 + 1];
end else begin
inc(a[k]);
b[k] := r - l + 1;
end;

end else begin

m := (l + r) shr 1;
update(k * 2, l, m, s);
if d[j].h > m then update(k * 2 + 1, m + 1, r, s);

if a[k] = 0 then b[k] := b[k * 2] + b[k * 2 + 1];

end;

end;

procedure main;
begin

qsort(1, n);

i := 1;
while i <= n do begin

j := i; max := b[1];
while (d[j].x = d.x) and (j <= n) do begin
if d[j].h > 0 then update(1, 1, 10100, d[j].s); inc(j);
end;
i := j;

if (b[1] <> max) then
if i <= n then write(d.x, ' ', b[1], ' ') else write(d.x, ' ', b[1]);

end;

end;

begin

// writeln; writeln;
read_data;
main;

end.

[frederic]

Hello,

i don't know why i get WA for this code. The code works on all data i have found in this board so far. Can you give me a hint , please?

(code deleted)

(Edit)
NM, i got ACC now

For me a critical input was:
1 1 2
1 3 2
1 2 2
2 3 4

Correct Answer:
1 3 4 0

Maybe this might help

[shaform]

I've tested my codes many times.
I even used some input files with random numbers, and I didn't find any problems.
But after I submited it, I got RE.
It said : Invalid memory reference
Well, I know there are some easier ways to solve The Skyline Problem, but I just want to know why this code couldn't work.

Code: Select all

Removed after solved.

[nev4]

This code is so big and it uses pointers to pointers, there is no wonder why RE. Try to code even without pointers if possible.
My solution for this to examine all blocks in a row and test if next is over current, if not test it comes from current's side, if not, does begin new block.

[shaform]

I think you are right.
Anyway, I finally got Accept.
Thanks.

[hedgehog1204]

This can be shorter. This is in Python, but can be easily converted to whatever:

Code: Select all

# Program that solves The Skyline Problem
# http://acm.uva.es/p/v1/105.html

max = 10000						# maximum x coordinates
h = [0 for i in range(max)]		# skyline heights for x=i

file = open('input.txt')
for line in file:						# initialize variables with data from file:
	vars = line.split()
	for i in range(int(vars[0]), int(vars[2])):	# update skyline hights
		if h[i] < int(vars[1]):
			h[i] = int(vars[1])
# print out the skyline:			
i = 0		
while h[i] == 0:
	i += 1
print i, h[i],
hi = h[i]
for j in range(i+2, max):
	if h[j] != hi:
		print j, h[j],
		hi = h[j]
file.close()

[hedgehog1204]

Code: Select all

max = 10000						
h = [0 for i in range(max)]		
file = open('input.txt')
for line in file:						
	vars = line.split()
	for i in range(int(vars[0]), int(vars[2])):	
		if h[i] < int(vars[1]):
			h[i] = int(vars[1])		
i = 0		
while h[i] == 0:
	i += 1
print i, h[i],
hi = h[i]
for j in range(i+2, max):
	if h[j] != hi:
		print j, h[j],
		hi = h[j]
file.close()

[hedgehog1204]

Code: Select all

max = 10000						
h = [0 for i in range(max)]		
file = open('input.txt')
for line in file:						
	vars = line.split()
	for i in range(int(vars[0]), int(vars[2])):	
		if h[i] < int(vars[1]):
			h[i] = int(vars[1])		
i = 0		
while h[i] == 0:
	i += 1
print i, h[i],
hi = h[i]
for j in range(i+2, max):
	if h[j] != hi:
		print j, h[j],
		hi = h[j]
file.close()

[hedgehog1204]

Code: Select all

max = 10000                  
h = [0 for i in range(max)]      
file = open('input.txt')
for line in file:                  
   vars = line.split()
   for i in range(int(vars[0]), int(vars[2])):   
      if h[i] < int(vars[1]):
         h[i] = int(vars[1])      
i = 0      
while h[i] == 0:
   i += 1
print i, h[i],
hi = h[i]
for j in range(i+2, max):
   if h[j] != hi:
      print j, h[j],
      hi = h[j]
file.close()

[hedgehog1204]

Code: Select all

max = 10000                  
h = [0 for i in range(max)]      
file = open('input.txt')
for line in file:                  
   vars = line.split()
   for i in range(int(vars[0]), int(vars[2])):   
      if h[i] < int(vars[1]):
         h[i] = int(vars[1])      
i = 0      
while h[i] == 0:
   i += 1
print i, h[i],
hi = h[i]
for j in range(i+2, max):
   if h[j] != hi:
      print j, h[j],
      hi = h[j]
file.close()