## 1232 - SKYLINE

Moderator: Board moderators

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 1232 - SKYLINE

Getting TLE
My Algo is :
1. Using Segment tree
2. In every range , I am keeping maximum & minimum height
3.updating ranges ...

Please , How to solve in time limit ??

New poster
Posts: 3
Joined: Thu Jul 09, 2015 5:20 am

### Re: 1232 - SKYLINE

You have to use lazy propagation to pass the time limit

Tanmoy1228
New poster
Posts: 10
Joined: Sat Jul 19, 2014 2:55 am

### Re: 1232 - SKYLINE

Using Segment tree In every range , I am keeping maximum & minimum height
and updating ranges ...
But WA
whats the wrong..

Code: Select all

``````#include<bits/stdc++.h>
#define ll long long int
#define MX 100009
#define mod 1000000007
#define ff first
#define ss second

using namespace std;

ll hh,ans,kk,xx,yy,n;

struct nnn
{
ll l,r,h;
};
nnn lll[100005];

struct data
{
ll sum,po,mx,mn;
};

data tree1[4*MX],tree2[4*MX];

ll querymini(ll node,ll b,ll e,ll i,ll j)
{
//    cout<<"querymini   "<<b<<" "<<e<<endl;
if(b>j || e<i)
return powl(10,10);
if(b>=i && e<=j)
return tree2[node].sum;
ll l,r,m;
l=2*node;
r=l+1;
m=(b+e)/2;

if(tree2[node].po==1)
{
tree2[l].sum=tree2[node].sum;
tree2[r].sum=tree2[node].sum;
tree2[node].po=0;
tree2[l].po=1;
tree2[r].po=1;
}

return min(querymini(l,b,m,i,j),querymini(r,m+1,e,i,j));
}

ll querymaxi(ll node,ll b,ll e,ll i,ll j)
{
if(b>j || e<i)
return 0;
if(b>=i && e<=j)
return tree1[node].sum;
ll l,r,m;
l=2*node;
r=l+1;
m=(b+e)/2;

if(tree1[node].po==1)
{
tree1[l].sum=tree1[node].sum;
tree1[r].sum=tree1[node].sum;
tree1[node].po=0;
tree1[l].po=1;
tree1[r].po=1;
}

return max(querymaxi(l,b,m,i,j),querymaxi(r,m+1,e,i,j));
}

void updatemini(ll node,ll b,ll e,ll i,ll j,ll val)
{
if(b>j || e<i)
return;
if(b>=i && e<=j)
{
tree2[node].sum=val;
tree2[node].po=1;
return;
}
ll l,r,m;
l=2*node;
r=l+1;
m=(b+e)/2;

if(tree2[node].po==1)
{
tree2[l].sum=tree2[node].sum;
tree2[r].sum=tree2[node].sum;
tree2[node].po=0;
tree2[l].po=1;
tree2[r].po=1;
}

updatemini(l,b,m,i,j,val);
updatemini(r,m+1,e,i,j,val);

tree2[node].sum=min(tree2[l].sum,tree2[r].sum);
}

void updatemaxi(ll node,ll b,ll e,ll i,ll j,ll val)
{
if(b>j || e<i)
return;
if(b>=i && e<=j)
{
tree1[node].sum=val;
tree1[node].po=1;
return;
}
ll l,r,m;
l=2*node;
r=l+1;
m=(b+e)/2;

if(tree1[node].po==1)
{
tree1[l].sum=tree1[node].sum;
tree1[r].sum=tree1[node].sum;
tree1[node].po=0;
tree1[l].po=1;
tree1[r].po=1;
}

updatemaxi(l,b,m,i,j,val);
updatemaxi(r,m+1,e,i,j,val);

tree1[node].sum=max(tree1[l].sum,tree1[r].sum);
}

void update(ll node,ll b,ll e,ll i,ll j,ll val)
{
//    cout<<b<<" "<<e<<" "<<i<<" "<<j<<endl;

if(b>j || e<i)
return;
//    cout<<querymaxi(1,1,MX,i,j)<<endl;
ll qq=querymaxi(1,1,n,i,j);
if(qq<=val)
{
ans+=(j-i);
//        if((i==xx && yy==j) || qq==val)
//            ans--;

//        cout<<i<<" "<<j<<" "<<ans<<endl;
updatemini(1,1,n,i,j,val);
updatemaxi(1,1,n,i,j,val);
return;
}
//    cout<<querymini(1,1,MX,i,j)<<endl;
if(querymini(1,1,n,i,j)>val)
return;

if(b+1==e){
ans++;
return;
}

ll l,r,m;
l=2*node;
r=l+1;
m=(b+e)/2;

if(i>=m)
update(r,m,e,i,j,val);
else if(j<=m)
update(l,b,m,i,j,val);
else
{
update(l,b,m,i,m,val);
update(r,m,e,m,j,val);
}
}

void up(ll l,ll r, ll h)
{
hh=h;
update(1,1,n,l,r,h);
}

int main()
{
ll t,T,m,i,j,l,r,h;
scanf("%lld",&t);

while(t--)
{
scanf("%lld",&m);
ans=0;
memset(tree1,0,sizeof tree1);
memset(tree2,0,sizeof tree2);
for(i=1; i<=m; i++)
{
scanf("%lld %lld %lld",&lll[i].l,&lll[i].r,&lll[i].h);
n=max(n,lll[i].r);
}
for(i=1; i<=n; i++)
{
l=lll[i].l;
r=lll[i].r;
h=lll[i].h;
xx=l;
yy=r;
up(l,r,h);
//            cout<<ans<<endl;
}
printf("%lld\n",ans);
}
scanf("%lld",&j);
return 0;
}
``````