Page 7 of 11

1

Posted: Tue Feb 28, 2006 10:40 am
by tmdrbs6584
Hi logic
Bye logic

Posted: Tue Feb 28, 2006 2:54 pm
by f.eliel
I don

Posted: Tue Feb 28, 2006 7:54 pm
by 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.

logic!

Posted: Fri Mar 03, 2006 8:26 am
by sds1100
logic

Posted: Fri Mar 03, 2006 8:37 am
by sds1100
i me too imlazy짱깨
sorry.
sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.

105 WA

Posted: Wed Apr 05, 2006 8:07 pm
by 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.

P 105 Why do i get WA?

Posted: Mon Jul 03, 2006 4:02 pm
by 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

[Solved]105 The Skyline Problem: Runtime Error

Posted: Tue Aug 08, 2006 2:14 pm
by 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.

Posted: Wed Aug 09, 2006 4:27 pm
by 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.

Posted: Fri Aug 11, 2006 8:09 am
by shaform
I think you are right.
Anyway, I finally got Accept.
Thanks.

This can be shorter

Posted: Mon Aug 21, 2006 7:48 am
by 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()

It can be shorter

Posted: Mon Aug 21, 2006 7:50 am
by 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()

This works for me

Posted: Mon Aug 21, 2006 7:53 am
by 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()

Try this approach:

Posted: Mon Aug 21, 2006 7:56 am
by 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()

Try this approach (Python):

Posted: Mon Aug 21, 2006 7:57 am
by 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()