1232 - SKYLINE

[Repon kumar Roy]

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

[Ahmad_Elsagheer]

You have to use lazy propagation to pass the time limit

[Tanmoy1228]

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;
}