oj.uz

Submission #1016599

# Submission time Handle Problem Language Result Execution time Memory
1016599 2024-07-08T08:45:58 Z simona1230 Wall (IOI14_wall) C++17
0 / 100
 514 ms 14260 KB 
#include "wall.h"
#include "bits/stdc++.h"
using namespace std;

struct node
{
    int l,r;
    int vl,tp;
    node() {}
    node(int lf,int rt,int _v,int _t)
    {
        l=lf;
        r=rt;
        vl=_v;
        tp=_t;
    }
};

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

    void push_lazy(int i,int l,int r)
    {
        if(t[i].tp==0)return;

        if(l!=r)
        {
            if(t[i].l==-1)children(i);
            int i1=t[i].l;
            int i2=t[i].r;

            if(t[i1].vl==-1||t[i1].vl<t[i].vl&&t[i].tp==1)
            {
                t[i1].vl=t[i].vl;
                t[i1].tp=t[i].tp;
            }

            if(t[i2].vl==-1||t[i2].vl<t[i].vl&&t[i].tp==1)
            {
                t[i2].vl=t[i].vl;
                t[i2].tp=t[i].tp;
            }

            if(t[i1].vl==-1||t[i1].vl>t[i].vl&&t[i].tp==2)
            {
                t[i1].vl=t[i].vl;
                t[i1].tp=t[i].tp;
            }

            if(t[i2].vl==-1||t[i2].vl>t[i].vl&&t[i].tp==2)
            {
                t[i2].vl=t[i].vl;
                t[i2].tp=t[i].tp;
            }
            if(t[i1].vl!=t[i2].vl||t[i1].tp!=t[i2].tp)
                t[i].vl=-1;
            else t[i].vl=t[i1].vl,t[i].tp=t[i1].tp;
        }
        t[i].tp=0;
    }

    void update(int i,int l,int r,int ql,int qr,int val,int type)
    {
        //cout<<val<<" "<<type<<endl;
        push_lazy(i,l,r);
        if(ql>qr)return;
        if(ql<=l&&r<=qr)
        {
            if(t[i].vl==-1||t[i].vl<val&&type==1)
            {
                //cout<<"in"<<endl;
                t[i].vl=val;
                t[i].tp=type;
            }
            if(t[i].vl==-1||t[i].vl>val&&type==2)
            {
                t[i].vl=val;
                t[i].tp=type;
            }
            //cout<<l<<" "<<r<<" "<<t[i].vl<<" "<<t[i].tp<<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(m+1,ql),qr,val,type);

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

        if(t[i1].vl!=t[i2].vl||t[i1].tp!=t[i2].tp)
            t[i].vl=-1;
        else t[i].vl=t[i1].vl,t[i].tp=t[i1].tp;
        //cout<<l<<" - "<<r<<" "<<t[i].vl<<" "<<t[i].tp<<endl;
    }

    void fix(int i,int l,int r)
    {
        if(t[i].l==-1)
        {
            for(int j=l; j<=r; j++)
                a[j]=t[i].vl;
            return;
        }
        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]);
    }

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

Compilation message

wall.cpp: In member function 'void tree::push_lazy(int, int, int)':
wall.cpp:42:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   42 |             if(t[i1].vl==-1||t[i1].vl<t[i].vl&&t[i].tp==1)
wall.cpp:48:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |             if(t[i2].vl==-1||t[i2].vl<t[i].vl&&t[i].tp==1)
wall.cpp:54:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   54 |             if(t[i1].vl==-1||t[i1].vl>t[i].vl&&t[i].tp==2)
wall.cpp:60:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   60 |             if(t[i2].vl==-1||t[i2].vl>t[i].vl&&t[i].tp==2)
wall.cpp: In member function 'void tree::update(int, int, int, int, int, int, int)':
wall.cpp:79:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   79 |             if(t[i].vl==-1||t[i].vl<val&&type==1)
wall.cpp:85:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   85 |             if(t[i].vl==-1||t[i].vl>val&&type==2)

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 2 ms 504 KB Output isn't correct
4 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 Correct 99 ms 8196 KB Output is correct
3 Correct 148 ms 4812 KB Output is correct
4 Incorrect 514 ms 14260 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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