oj.uz

Submission #1016889

# Submission time Handle Problem Language Result Execution time Memory
1016889 2024-07-08T14:36:43 Z simona1230 Wall (IOI14_wall) C++17
0 / 100
 120 ms 8260 KB 
#include "wall.h"
#include "bits/stdc++.h"
using namespace std;

struct node
{
    int l,r;
    int v1,v2;
    node() {}
    node(int lf,int rt,int _v1,int _v2)
    {
        l=lf;
        r=rt;
        v1=_v1;
        v2=_v2;
    }
};

int a[2000001],b[2000001];
struct tree
{
    vector<node> t= {{-1,-1,0,(int)1e9}};
    tree() {}
    void children(int i)
    {
        t.push_back({-1,-1,0,(int)1e9});
        t[i].l=t.size()-1;
        t.push_back({-1,-1,0,(int)1e9});
        t[i].r=t.size()-1;
    }

    void push_lazy(int i,int l,int r)
    {
        if(l==r)return;

        if(t[i].l==-1)children(i);

        int i1=t[i].l,i2=t[i].r;

        //cout<<l<<" "<<r<<" "<<t[i].v1<<" "<<t[i].v2<<endl;
        //cout<<t[i1].v1<<" "<<t[i1].v2<<endl;
        if(t[i].v1>t[i1].v2)
        {
            t[i1].v1=t[i1].v2=t[i].v1;
        }
        else if(t[i].v2<t[i1].v1)
        {
            t[i1].v1=t[i1].v2=t[i].v2;
        }
        else
        {
            t[i1].v1=max(t[i].v1,t[i1].v1);
            t[i1].v2=min(t[i].v2,t[i1].v2);
        }

        if(t[i].v1>t[i2].v2)
        {
            t[i2].v1=t[i2].v2=t[i].v1;
        }
        else if(t[i].v2<t[i2].v1)
        {
            t[i2].v1=t[i2].v2=t[i].v2;
        }
        else
        {
            t[i2].v1=max(t[i].v1,t[i2].v1);
            t[i2].v2=min(t[i].v2,t[i2].v2);
        }
        //cout<<t[i1].v1<<" "<<t[i1].v2<<endl;

        t[i].v1=0;
        t[i].v2=1e9;
    }

    void update(int i,int l,int r,int ql,int qr,int val,int type)
    {
        push_lazy(i,l,r);
        if(ql>qr)return;

        if(ql<=l&&r<=qr)
        {
            if(type==1)
            {
                if(val>t[i].v2)
                {
                    t[i].v1=val;
                    t[i].v2=1e9;
                }
                else
                {
                    //cout<<"in"<<endl;
                    t[i].v1=max(t[i].v1,val);
                }
            }
            else
            {
                if(t[i].v1>val)
                {
                    t[i].v1=0;
                    t[i].v2=val;
                }
                else t[i].v2=min(t[i].v2,val);
            }
            push_lazy(i,l,r);
            //cout<<i<<" "<<t[i].v1<<" "<<t[i].v2<<endl;
            return;
        }
        int m=(l+r)/2;
        if(t[i].l==-1)children(i);
        update(t[i].l,l,m,ql,min(qr,m),val,type);
        update(t[i].r,m+1,r,max(ql,m+1),qr,val,type);
    }

    void fix(int i,int l,int r)
    {
        if(t[i].l==-1)
        {
            //cout<<i<<endl;
            for(int j=l;j<=r;j++)
                a[j]=t[i].v1;
            return;
        }
        //cout<<l<<" "<<r<<endl;
        push_lazy(i,l,r);
        int m=(l+r)/2;
        fix(t[i].l,l,m);
        fix(t[i].r,m+1,r);
    }
};

tree t;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for(int i=0; i<k; i++)
    {
        //cout<<height[i]<<" "<<op[i]<<endl;
        t.update(0,0,n-1,left[i],right[i],height[i],op[i]);
        //cout<<endl;
    }

    t.fix(0,0,n-1);
    for(int i=0; i<n; i++)
        finalHeight[i]=a[i];
}
/*
10 1
1 0 9 1
*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 120 ms 8260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 2 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -