Submission #472568

#	Time	Username	Problem	Language	Result	Execution time	Memory
472568		Haidara	Wall (IOI14_wall)	C++17	0 / 100	754 ms	13864 KiB

wall

/** * * * * * * * * * * * * * * **\
     *                               *
     *    Author: Haidara Nassour    *
     * Coded in: 2021\09\12 HH:MM:SS *
     *           Lang: C++           *
     *                               *
    \** * * * * * * * * * * * * * * **/
    #include<bits/stdc++.h>
    #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    #define test int tests;cin>>tests;while(tests--)
    #define itn int
    #define rep(i,x,n) for(int i=(x);i<(n);i++)
    #define FOR(i,n) rep(i,0,n)
    #define per(i,x,n) for(int i=(x);i>(n);i--)
    #define ROF(i,x) for(int i=x;i>=0;i--)
    #define v(i) vector< i >
    #define p(i,j) pair< i , j >
    #define pii pair<int,int>
    #define m(i,j) map< i , j >
    #define um(i,j) unordered_map< i , j >
    #define max_heap(i) priority_queue< i >
    #define min_heap(i) priority_queue< i , vector< i > ,greater< i > >
    #define ff first
    #define all(x) x.begin(),x.end()
    #define rall(x) x.rbegin(),x.rend()
    #define ss second
    #define pp push_back
    #define debug(x) cout<<#x<<" ";
    using namespace std;
    const int inf=1LL<<30LL;
    const int mod=998244353;
    const int maxn=200200;
    int n;
    struct node
    {
        int setdown=inf,setup=0,maxtall=inf,mintall=0,last=0;
        /// setdown -> all buildings greater than it will equal to it
        /// setup -> all buildings smaller than it will equal to it
    } st[maxn*4];
    bool add=0;
    int val;
    void pull(int inx,int l,int r)
    {
        st[inx].mintall=max(st[inx].mintall,st[inx].setup);
        st[inx].maxtall=min(st[inx].maxtall,st[inx].setdown);
        if(add)
            st[inx].last=0;
        else
            st[inx].last=1;
        if(l!=r)
        {
            st[inx*2].setup=max(st[inx*2].setup,st[inx].setup);
            st[inx*2].setdown=min(st[inx*2].setdown,st[inx].setdown);
            st[inx*2+1].setup=max(st[inx*2+1].setup,st[inx].setup);
            st[inx*2+1].setdown=min(st[inx*2+1].setdown,st[inx].setdown);
        }
        st[inx].setdown=inf;
        st[inx].setup=0;
    }
    void update(int ul,int ur,int l=1,int r=n,int inx=1)
    {
        pull(inx,l,r);
        if(ul<=l&&r<=ur)
        {
            /// setdown -> all buildings greater than it will equal to it
            /// setup -> all buildings smaller than it will equal to it
            if(add)
                st[inx].setup=val;
            else
                st[inx].setdown=val;
            pull(inx,l,r);
            return ;
        }
        if(l>ur||ul>r)
            return ;
        int mid=l+(r-l)/2;
        update(ul,ur,l,mid,inx*2);
        update(ul,ur,mid+1,r,inx*2+1);
    }
    int query(int pos,int l=1,int r=n,int inx=1)
    {
        pull(inx,l,r);
        if(l==r)
        {
            if(!st[inx].last)
                return st[inx].mintall;
            return st[inx].maxtall;
        }
        int mid=l+(r-l)/2;
        if(pos<=mid)
            return query(pos,l,mid,inx*2);
        return query(pos,mid+1,r,inx*2+1);
    }
    void buildWall(int sz, int k, int op[], int left[], int right[],int height[], int finalHeight[])
    {
        n=sz;
        FOR(i,k)
        {
            right[i]++;
            left[i]++;
            add=0;
            val=height[i];
            if(op[i]==1)
                add=1,update(left[i],right[i]);
            else
                update(left[i],right[i]);
        }
        FOR(i,n)
        finalHeight[i]=query(i+1);
    }

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39