oj.uz

Submission #1016891

# Submission time Handle Problem Language Result Execution time Memory
1016891 2024-07-08T14:38:34 Z simona1230 Wall (IOI14_wall) C++17
100 / 100
 710 ms 84100 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=val;
                }
                else
                {
                    //cout<<"in"<<endl;
                    t[i].v1=max(t[i].v1,val);
                }
            }
            else
            {
                if(t[i].v1>val)
                {
                    t[i].v1=val;
                    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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 6 ms 2920 KB Output is correct
5 Correct 7 ms 3036 KB Output is correct
6 Correct 4 ms 3036 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 98 ms 10324 KB Output is correct
3 Correct 159 ms 6344 KB Output is correct
4 Correct 471 ms 14704 KB Output is correct
5 Correct 270 ms 14464 KB Output is correct
6 Correct 266 ms 14268 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 6 ms 3036 KB Output is correct
5 Correct 4 ms 3036 KB Output is correct
6 Correct 5 ms 3036 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 84 ms 10228 KB Output is correct
9 Correct 170 ms 6484 KB Output is correct
10 Correct 462 ms 14104 KB Output is correct
11 Correct 316 ms 14360 KB Output is correct
12 Correct 288 ms 14280 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 101 ms 10108 KB Output is correct
15 Correct 37 ms 3784 KB Output is correct
16 Correct 597 ms 14468 KB Output is correct
17 Correct 272 ms 14712 KB Output is correct
18 Correct 271 ms 14268 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 6 ms 3036 KB Output is correct
5 Correct 5 ms 3036 KB Output is correct
6 Correct 5 ms 3036 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 82 ms 10104 KB Output is correct
9 Correct 151 ms 6344 KB Output is correct
10 Correct 453 ms 14012 KB Output is correct
11 Correct 292 ms 14724 KB Output is correct
12 Correct 267 ms 15292 KB Output is correct
13 Correct 1 ms 2648 KB Output is correct
14 Correct 84 ms 10264 KB Output is correct
15 Correct 31 ms 3660 KB Output is correct
16 Correct 603 ms 14356 KB Output is correct
17 Correct 279 ms 15296 KB Output is correct
18 Correct 275 ms 14264 KB Output is correct
19 Correct 663 ms 84100 KB Output is correct
20 Correct 681 ms 80920 KB Output is correct
21 Correct 642 ms 82588 KB Output is correct
22 Correct 677 ms 80276 KB Output is correct
23 Correct 642 ms 80280 KB Output is correct
24 Correct 645 ms 80792 KB Output is correct
25 Correct 654 ms 80788 KB Output is correct
26 Correct 710 ms 82836 KB Output is correct
27 Correct 680 ms 82976 KB Output is correct
28 Correct 654 ms 80792 KB Output is correct
29 Correct 655 ms 79768 KB Output is correct
30 Correct 660 ms 80504 KB Output is correct