105 - The Skyline Problem

[yan8381]

you vector length is 500, I think that is too small, because "All coordinates of buildings are positive integers less than 10,000 ". so I denfine the vector is 100002,that is better.

and another problem is your output.
for example, your output is: 2^3^4^('^'means space)
but,the output should be:2^3^4'/n'

[RyanCHEN]

I sloved the problem already!

I got the error since I used the member fuction of vector .at()
the system didnt like that:)

thank you Yan anyway!:)

[maxpayne]

I don't understand why I got runtime error for my program. Here it is:
[cpp]
#include <iostream>
#include <string>
using namespace std;

class skylines {
unsigned int left[5000];
unsigned int height[5000];
unsigned int right[5000];
unsigned int most;
static unsigned int i;
public:
skylines() : most(0) {
memset(left,0,sizeof(left));
memset(height,0,sizeof(height));
memset(right,0,sizeof(right));
}
void input(const unsigned int l, const unsigned int h, const unsigned int r);
void answer();
};

unsigned int skylines::i = 0;

void skylines::answer() {
unsigned int j=0;
short int flag=0,same=0;
unsigned int temp=0,left_temp=0,right_temp=0;

for(unsigned int i=left[0]; i<=most; i++) {
j=0;
if(temp==0) {
while((left[j]<=i)&&(left[j]!=0)) {
if(right[j]<i) {
j++;
continue;
}
else {
if(temp<height[j]) {
temp = height[j];
left_temp = left[j];
right_temp = right[j];
flag=1;
}
j++;
}
}
if(flag==1) {
cout << i << " " << temp << " " ;
flag=0;
if(left_temp==right_temp) i--;
}
}
else {
if(i==right_temp) {
temp = left_temp = right_temp = 0;
while((left[j]<=i)&&(left[j]!=0)) {
if(right[j]<=i) {
j++;
continue;
}
else {
if(temp<height[j]) {
temp = height[j];
left_temp = left[j];
right_temp = right[j];
}
j++;
}

}
cout << i << " " << temp << " " ;
}
else {
while((left[j]<=i)&&(left[j]!=0)) {
if(right[j]<i) {
j++;
continue;
}
else {
if(temp<height[j]) {
temp = height[j];
left_temp = left[j];
right_temp = right[j];
flag=1;
}
j++;
}

}
if(flag==1) {
cout << i << " " << temp << " " ;
flag=0;
if(left_temp==right_temp) i--;
}
}
}//end of else if
}//end of for

}

void skylines::input(const unsigned int l, const unsigned int h, const unsigned int r ) {
left = l;
height = h;
right = r;
if(most<right) most = right;
i++;
}

int main() {
skylines user;

unsigned int l,h,r;

while(cin >> l >> h >> r) {
user.input(l,h,r);
}

user.answer();
int x;
cin >> x;

}
[/cpp]
Thanks for your helping.

[scruff]

Well, it died with an "invalid memory reference" so check your indexes on your arrays and verify they don't go outside their bounds

[maxpayne]

Thank you. I solved my problem now although why I got Presentation Error is still mistery for me.

[scruff]

Well, i have a couple of comments. I have not run your code yet but it seems that it always outputs a blank space after every cout which is fine until the last entry and then you should not print the space. This will give a presentation error. The second is what is that last cin in your main() for?

[Gazi Shaheen Hossain]

Why this gives WA?
help me.
[cpp]
#include "stdio.h"

void main()
{

int arr[10000]={0},i,L,H,R,Rm=0;
while(scanf("%d %d %d",&L,&H,&R)==3)
{
if(Rm<R)Rm=R;
for(i=2*L;i<=2*R;i++)
if(arr<H)
arr=H;
}
i=0;
if(arr[0]!=0)printf("0 %d ",arr[0]);
char flag=0;
for(i=1;i<=2*(Rm+1);i++)
{

if(arr>arr[i-1])
{if(flag)printf(" "); flag=1;
printf("%d %d",i/2,arr);}
else if(arr<arr[i-1])
{if(flag)printf(" "); flag=1;
printf("%d %d",(i-1)/2,arr);}

}
}
[/cpp]

[afonsocsc]

Hello,
You have an array of 10000, but you use 2*L and 2*R, since the numbers for L and R will be as high as 9999, your program will be accessing memory outside of the array.

for example, with this input:
4090 5000 5000

your program gives:
4090 5000 5000 1073833120 5000 -1073744880 5001 -1073744764

Hope it helps

[efr_shovo]

i got p.e. why? Pleaze help me
#include<stdio.h>

int a[20000];
int l,r,h,i,j,max=0,mutex=0;

void main()
{
while(3==scanf("%d %d %d",&l,&h,&r))
{
for(i=l;i<=r;i++)
if(a<h)
a=h;
}

for(j=0;j<=i;j++)
{
if(a[j]>a[j+1])
{
max=j;
mutex=1;
}
else if(a[j]<a[j+1])
{
max=j+1;
mutex=1;
}
if(mutex==1)
{
printf("%d %d ",max,a[j+1]);
mutex=0;
}
}
printf("\n");
}

[Dominik Michniewski]

you print unnecessary space at end of the line. Try to avoid this character, and I think you got Acc without PE.

Best regards
DM

[straggler73]

I get PE ... Please Help
#include <stdio.h>

#define MAX 10000

int height[MAX+1];

int main()
{
int i;
int li, hi, ri;

for(i=0; i<= MAX; i++)
{
height = 0;
}

while (scanf("%d %d %d\n",&li, &hi, &ri)==3){
for(i=li; i < ri; i++)
{
if (height < hi)
height = hi;
}
}

for(i=1; i<= MAX; i++)
{
if (height[i-1] != height)
{
printf("%d %d ", i, height);
}
}
return 0;
}

[Mohammad Mahmudur Rahman]

The problem statement says that -

The coordinates must be separated by a blank space.

But I think u r printing an space after the last co-ordinate, too. Hope it helps.

[lazenca]

I tested some data with this code...but I got WA...
plz help me..

Code: Select all

#include <stdio.h>
#include <stdlib.h>      /*   malloc   */ 


typedef struct buildingTriple *pBuildingTriple;
typedef struct buildingTriple {
	unsigned int   left;           /*   left coordinate of building   */
	unsigned int   right;          /*   right coordinate of building   */
	unsigned int   height;         /*   height of building   */
	pBuildingTriple next;          /*   link to next node   */
	pBuildingTriple back;          /*   link to back node   */
} buildingTriple;



void   insert_to_list(pBuildingTriple ptr, pBuildingTriple node);


int main()
{
	buildingTriple   head;        /*   list for buildings   */
	buildingTriple   in_node;       /*   inputed coordinates of building   */

	/*   temp variable   */
	pBuildingTriple   w_ptr = &head;
	unsigned int   temp;
	unsigned int   pre_right_coord;    

	
	/*   circular linked list=_=;;;   */
	head.back = head.next = &head;    



	while (scanf("%u %u %u", &in_node.left, &in_node.height, &in_node.right) == 3)
.
.
.
.
.

[chunyi81]

The error in your code is obvious - check the way you output. You are printing everything on one line, that is the main reason for your code getting WA.

[c]



/************************************************************************/
/* OUTPUT PART */
/************************************************************************/
for (w_ptr = head.next; w_ptr != &head; w_ptr = w_ptr->next)
{
if (w_ptr == head.next || w_ptr->left >= pre_right_coord)
{
printf("%u %u ", w_ptr->left, w_ptr->height);
pre_right_coord = w_ptr->right;
}
else
{
printf("%u 0 ", pre_right_coord);
}
}
printf("%u 0\n", pre_right_coord);
[/c]

Add in a \n - newline character for the last printf as shown above and your code should work fine.

[lazenca]

thanks for your advice...

now, I got AC... It was so hard to me....=_=;;;

Finally I rebuild my code..including output part.
The main problem was linked list part. hm..


well, I have a question about free()...
If I use free(), the program run faster or slower?
I tested that, but can't find difference...@_@