Submission #1275606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275606		danglayloi1	Wall (IOI14_wall)	C++20	100 / 100	451 ms	67020 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=2e6+5;
int res[nx], lmax[nx<<2], lmin[nx<<2];
void down(int id)
{
    if(lmax[id]!=lmin[id])
        return;
    lmin[id<<1]=lmax[id<<1]=lmin[id];
    lmin[id<<1|1]=lmax[id<<1|1]=lmin[id];
}
void update(int id, int l, int r, int u, int v, int val)
{
    if(val<=lmin[id] || l>v || r<u)
        return;
    if(l>=u && r<=v && val>lmax[id])
    {
        lmin[id]=lmax[id]=val;
        return;
    }
    int mid=(l+r)>>1;
    down(id);
    update(id<<1, l, mid, u, v, val);
    update(id<<1|1, mid+1, r, u, v, val);
    lmin[id]=min(lmin[id<<1], lmin[id<<1|1]);
    lmax[id]=max(lmax[id<<1], lmax[id<<1|1]);
}
void update1(int id, int l, int r, int u, int v, int val)
{
    if(val>=lmax[id] || l>v || r<u)
        return;
    if(l>=u && r<=v && val<lmin[id])
    {
        lmin[id]=lmax[id]=val;
        return;
    }
    int mid=(l+r)>>1;
    down(id);
    update1(id<<1, l, mid, u, v, val);
    update1(id<<1|1, mid+1, r, u, v, val);
    lmin[id]=min(lmin[id<<1], lmin[id<<1|1]);
    lmax[id]=max(lmax[id<<1], lmax[id<<1|1]);
}
void push(int id, int l, int r)
{
    if(l==r)
    {
        res[l]=lmin[id];
        return;
    }
    int mid=(l+r)/2;
    down(id);
    push(id<<1, l, mid);
    push(id<<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 < k; i++)
    {
        left[i]++, right[i]++;
        if(op[i]==1) update(1, 1, n, left[i], right[i], height[i]);
        else update1(1, 1, n, left[i], right[i], height[i]);
    }
    push(1, 1, n);
    for(int i = 1; i <= n; i++)
        finalHeight[i-1]=res[i];
}

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