### 1

Posted:

**Tue Feb 28, 2006 10:40 am**Hi logic

Bye logic

Bye logic

Page **7** of **11**

Posted: **Tue Feb 28, 2006 10:40 am**

Hi logic

Bye logic

Bye logic

Posted: **Tue Feb 28, 2006 2:54 pm**

I don

Posted: **Tue Feb 28, 2006 7:54 pm**

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.

Remove your code after u get AC.

Posted: **Fri Mar 03, 2006 8:26 am**

logic

Posted: **Fri Mar 03, 2006 8:37 am**

i me too imlazy짱깨

sorry.

sorry i don't know your program..

sorry.sorry.sorry.sorry.sorry.

sorry.

sorry i don't know your program..

sorry.sorry.sorry.sorry.sorry.

Posted: **Wed Apr 05, 2006 8:07 pm**

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

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.

Posted: **Mon Jul 03, 2006 4:02 pm**

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

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

Posted: **Tue Aug 08, 2006 2:14 pm**

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.

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.
```

Posted: **Wed Aug 09, 2006 4:27 pm**

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.

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.

Posted: **Fri Aug 11, 2006 8:09 am**

I think you are right.

Anyway, I finally got Accept.

Thanks.

Anyway, I finally got Accept.

Thanks.

Posted: **Mon Aug 21, 2006 7:48 am**

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()
```

Posted: **Mon Aug 21, 2006 7:50 am**

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()
```

Posted: **Mon Aug 21, 2006 7:53 am**

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()
```

Posted: **Mon Aug 21, 2006 7:56 am**

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()
```

Posted: **Mon Aug 21, 2006 7:57 am**

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()
```