oj.uz

Submission #1016580

# Submission time Handle Problem Language Result Execution time Memory
1016580 2024-07-08T08:29:03 Z simona1230 Wall (IOI14_wall) C++17
0 / 100
 120 ms 8072 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=1;
            }

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

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

            if(t[i2].vl==-1||t[i2].vl>t[i].vl&&t[i].tp==2)
            {
                t[i2].vl=t[i].vl;
                t[i2].tp=2;
            }
            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)
    {
        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)
            {
                t[i].vl=val;
                t[i].tp=1;
            }
            if(t[i].vl==-1||t[i].vl>val&&type==2)
            {
                t[i].vl=val;
                t[i].tp=2;
            }

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

    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++)
    {
        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:78:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   78 |             if(t[i].vl==-1||t[i].vl<val&&type==1)
wall.cpp:83:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   83 |             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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 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 78 ms 8072 KB Output is correct
3 Incorrect 120 ms 4732 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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