Submission #849262

#	Time	Username	Problem	Language	Result	Execution time	Memory
849262		abcvuitunggio	벽 (IOI14_wall)	C++17	100 / 100	720 ms	140176 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct T{
    int l,r;
}st[8000001],lazy[8000001];
int res[2000001];
T operator +(T a, T b){
    return {min(a.l,b.l),max(a.r,b.r)};
}
T operator *(T a, T b){
    return {min(max(a.l,b.l),b.r),min(max(a.r,b.l),b.r)};
}
void down(int node, int l, int r){
    if (l==r)
        return;
    st[node<<1]=st[node<<1]*lazy[node];
    lazy[node<<1]=lazy[node<<1]*lazy[node];
    st[node<<1|1]=st[node<<1|1]*lazy[node];
    lazy[node<<1|1]=lazy[node<<1|1]*lazy[node];
    lazy[node]={0,100000};
}
void update(int node, int l, int r, int u, int v, T t){
    if (l>v||r<u||l>r)
        return;
    if (l>=u&&r<=v){
        st[node]=st[node]*t;
        lazy[node]=lazy[node]*t;
        return;
    }
    down(node,l,r);
    int mid=(l+r)>>1;
    update(node<<1,l,mid,u,v,t);
    update(node<<1|1,mid+1,r,u,v,t);
    st[node]=st[node<<1]+st[node<<1|1];
}
void dfs(int node, int l, int r){
    if (l==r){
        res[l]=st[node].l;
        return;
    }
    down(node,l,r);
    int mid=(l+r)>>1;
    dfs(node<<1,l,mid);
    dfs(node<<1|1,mid+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i=0;i<=n*4;i++)
        lazy[i]={0,100000};
    for (int i=0;i<k;i++){
        T t;
        if (op[i]==1)
            t={height[i],100000};
        else
            t={0,height[i]};
        update(1,0,n-1,left[i],right[i],t);
    }
    dfs(1,0,n-1);
    for (int i=0;i<n;i++)
        finalHeight[i]=res[i];
    return;
}

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