Submission #378079

#	Time	Username	Problem	Language	Result	Execution time	Memory
378079		ScarletS	Wall (IOI14_wall)	C++17	100 / 100	847 ms	59244 KiB

wall

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e5, mn = 2e6+7;
int seg[mn<<2][2];

void passDown(int i)
{
    for (int j=i*2+1;j<i*2+3;++j)
    {
        seg[j][0]=max(seg[j][0],seg[i][0]);
        seg[j][1]=max(seg[j][0],seg[j][1]);
        seg[j][1]=min(seg[j][1],seg[i][1]);
        seg[j][0]=min(seg[j][0],seg[j][1]);
    }
    seg[i][0]=0;
    seg[i][1]=INF;
}

void update(int i, int l, int r, int op, int L, int R, int h)
{
    if (R<l||r<L)
        return;
    if (L<=l&&r<=R)
    {
        if (op==1)
        {
            seg[i][0]=max(seg[i][0],h);
            seg[i][1]=max(seg[i][1],h);
        }
        else
        {
            seg[i][0]=min(seg[i][0],h);
            seg[i][1]=min(seg[i][1],h);
        }
        return;
    }
    passDown(i);
    update(i*2+1,l,l+(r-l)/2,op,L,R,h);
    update(i*2+2,l+(r-l)/2+1,r,op,L,R,h);
}

void calc(int i, int l, int r, int ans[])
{
    if (l==r)
    {
        ans[l]=seg[i][0];
        return;
    }
    passDown(i);
    calc(i*2+1,l,l+(r-l)/2,ans);
    calc(i*2+2,l+(r-l)/2+1,r,ans);
}

void buildWall(int n, int k, int op[], int l[], int r[],
int h[], int ans[])
{
    for (int i=0;i<k;++i)
        update(0,0,n-1,op[i],l[i],r[i],h[i]);
    calc(0,0,n-1,ans);
}

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