## 105 - The Skyline Problem

Moderator: Board moderators

tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

### 1

Hi logic
Bye logic

f.eliel
New poster
Posts: 10
Joined: Wed Feb 08, 2006 4:31 pm
I don

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
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.
Where's the "Any" key?

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

### logic!

logic

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm
i me too imlazy짱깨
sorry.
sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.

coldfire
New poster
Posts: 8
Joined: Sat Mar 12, 2005 4:47 pm

### 105 WA

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;

//var f: text;
begin

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

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

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;
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 <> max) then
if i <= n then write(d.x, ' ', b, ' ') else write(d.x, ' ', b);

end;

end;

begin

// writeln; writeln;
main;

end.

frederic
New poster
Posts: 1
Joined: Mon Jul 03, 2006 1:31 am

### P 105 Why do i get WA?

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

1 3 4 0

Maybe this might help

shaform
New poster
Posts: 4
Joined: Tue Aug 08, 2006 1:55 pm

### [Solved]105 The Skyline Problem: Runtime Error

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.
``````
Last edited by shaform on Fri Aug 11, 2006 8:04 am, edited 2 times in total.

nev4
New poster
Posts: 15
Joined: Sun Apr 30, 2006 10:19 am
Location: Lithuania
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
New poster
Posts: 4
Joined: Tue Aug 08, 2006 1:55 pm
I think you are right.
Anyway, I finally got Accept.
Thanks.

hedgehog1204
New poster
Posts: 13
Joined: Sat Oct 04, 2003 12:03 am
Location: USA
Contact:

### This can be shorter

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), int(vars)):	# update skyline hights
if h[i] < int(vars):
h[i] = int(vars)
# 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
New poster
Posts: 13
Joined: Sat Oct 04, 2003 12:03 am
Location: USA
Contact:

### It can be shorter

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), int(vars)):
if h[i] < int(vars):
h[i] = int(vars)
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
New poster
Posts: 13
Joined: Sat Oct 04, 2003 12:03 am
Location: USA
Contact:

### This works for me

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), int(vars)):
if h[i] < int(vars):
h[i] = int(vars)
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
New poster
Posts: 13
Joined: Sat Oct 04, 2003 12:03 am
Location: USA
Contact:

### Try this approach:

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), int(vars)):
if h[i] < int(vars):
h[i] = int(vars)
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
New poster
Posts: 13
Joined: Sat Oct 04, 2003 12:03 am
Location: USA
Contact:

### Try this approach (Python):

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), int(vars)):
if h[i] < int(vars):
h[i] = int(vars)
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()
``````