Submission #881836

#	Time	Username	Problem	Language	Result	Execution time	Memory
881836		cpptowin	Wall (IOI14_wall)	C++17	0 / 100	409 ms	26048 KiB

wall

#include<bits/stdc++.h>
#include<wall.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define inf 1000000000
using namespace std;
int st[maxn];
int lazy1[maxn],lazy[maxn];
void down(int id)
{
    if(lazy[id])
    {
        st[id << 1] = max(st[id << 1],lazy[id]);
        st[id << 1 | 1] = max(st[id << 1 | 1],lazy[id]);
        lazy[id << 1] = max(lazy[id],lazy[id << 1]);
        lazy[id << 1 | 1] = max(lazy[id << 1 | 1],lazy[id]);
        lazy1[id << 1] = lazy1[id << 1 | 1] = -1;
        lazy[id] = 0;
    }
    if(lazy1[id] != -1)
    {
        st[id << 1] = min(st[id << 1],lazy1[id]);
        st[id << 1 | 1] = min(st[id << 1 | 1],lazy1[id]);
        if(lazy1[id << 1] == -1) lazy1[id << 1] = lazy1[id];
        else  lazy1[id << 1] = min(lazy1[id],lazy1[id << 1]);
        if(lazy1[id << 1 | 1] == -1) lazy1[id << 1 | 1] = lazy1[id];
        else  lazy1[id << 1 | 1] = min(lazy1[id],lazy1[id << 1 | 1]);
        lazy1[id] = -1;
        lazy[id << 1] = lazy[id << 1 | 1] = 0;
    }
}
void update_max(int id,int l,int r,int u,int v,int val)
{
    if(l > v or r < u) return;
    if(u <= l and r <= v)
    {
        st[id] = max(st[id],val);
        lazy[id] = max(lazy[id],val);
        lazy1[id] = -1;
        return;
    }
    down(id);
    int mid = (l + r) >> 1;
    update_max(id << 1,l,mid,u,v,val);
    update_max(id << 1 | 1,mid + 1,r,u,v,val);
    st[id] = max(st[id << 1],st[id << 1 | 1]);
}
void update_down(int id,int l,int r,int u,int v,int val)
{
    if(l > v or r < u) return;
    if(u <= l and r <= v)
    {
        st[id] = min(st[id],val);
        if(lazy1[id] != -1)
            lazy1[id] = min(lazy1[id],val);
        else lazy1[id] = val;
        lazy[id] = 0;
        return;
    }
    down(id);
    int mid = (l + r) >> 1;
    update_down(id << 1,l,mid,u,v,val);
    update_down(id << 1 | 1,mid + 1,r,u,v,val);
    st[id] = max(st[id << 1],st[id << 1 | 1]);
}
int get(int id,int l,int r,int u,int v)
{
    if(l > v or r < u) return 0;
    if(u <= l and r <= v) return st[id];
    down(id);
    int mid = (l + r) >> 1;
    return max(get(id << 1,l,mid,u,v),get(id << 1 | 1,mid + 1,r,u,v));
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[])
{
    memset(lazy1,-1,sizeof lazy1);
    fo(i,0,k - 1)
    {
        if(op[i] == 1) update_max(1,1,n,left[i] + 1,right[i] + 1,height[i]);
        else update_down(1,1,n,left[i] + 1,right[i] + 1,height[i]);
    }
    fo(i,0,n - 1) finalHeight[i] = get(1,1,n,i + 1,i + 1);
}

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