Submission #1131956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131956		anngela	Wall (IOI14_wall)	C++20	100 / 100	383 ms	117828 KiB

wall

#include <bits/stdc++.h>

using namespace std;
#define lc (id<<1)
#define rc ((id<<1)|1)
#define ii pair<int,int>
#define fi first
#define se second
const int maxn=2e6+7;
const int inf=1e9+7;
int res[maxn];
struct segtree{
    int n;
    vector<int>t;
    vector<pair<int,int>>lazy;
    segtree(){}
    segtree(int n):n(n),t(n*4+7,0),lazy(n*4+7,{0,0}){}
    void pulldec(int x,int k)
    {
        t[x]=min(t[x],k);
        lazy[x].fi=min(lazy[x].fi,k);
        lazy[x].se=min(lazy[x].se,k);
    }
    void pulladd(int x,int k)
    {
        t[x]=max(t[x],k);
        lazy[x].fi=max(lazy[x].fi,k);
        lazy[x].se=max(lazy[x].se,k);
    }
    void down(int id){
        if(lazy[id].fi!=-inf){
            pulladd(lc,lazy[id].fi);
            pulladd(rc,lazy[id].fi);
        }
        if(lazy[id].se!=inf){
            pulldec(lc,lazy[id].se);
            pulldec(rc,lazy[id].se);
        }
        lazy[id]={-inf,inf};
    }
    void up(int id,int l,int r,int u,int v,int k,int type){
        if(l>v||r<u){
            return;
        }
        if(u<=l&&r<=v){
            if(type==1)pulladd(id,k);
            else pulldec(id,k);
            return;
        }
        if(l!=r)down(id);
        int m=(l+r)/2;
        up(lc,l,m,u,v,k,type);
        up(rc,m+1,r,u,v,k,type);
    }
    void get(int id,int l,int r){
        if(l==r){
            res[l]=t[id];
            return;
        }
        if(l!=r)down(id);
        int m=(l+r)/2;
        get(lc,l,m);
        get(rc,m+1,r);
    }
    void up(int u,int v,int k,int type){up(1,0,n-1,u,v,k,type);}
    void get(){get(1,0,n-1);}
};
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[])
{
    segtree t(n);
    for(int i=0;i<k;i++){
        t.up(left[i],right[i],height[i],op[i]);
    }
    t.get();
    for(int i=0;i<n;i++)finalHeight[i]=res[i];

}

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