Submission #1218246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218246		Hamed_Ghaffari	Wall (IOI14_wall)	C++20	100 / 100	390 ms	59404 KiB

wall

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

using pii = pair<int, int>;

#define X first
#define Y second
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 2e6+6;

int n;
pii lz[MXN<<2];

void build(int l=0, int r=n, int id=1) {
    lz[id] = {0, 1};
    if(r-l == 1) return;
    build(l, mid, lc);
    build(mid, r, rc);
}
inline void apply(pii x, int id) {
    if(x.X >= lz[id].X) {
        if(lz[id].Y <= x.X) lz[id] = {x.X, x.X+1};
        else lz[id] = {x.X, min(x.Y, lz[id].Y)};
    }
    else lz[id] = {min(lz[id].X, x.Y-1), min(x.Y, lz[id].Y)};
}
inline void push(int id) {
    apply(lz[id], lc);
    apply(lz[id], rc);
    lz[id] = {-1, 100001};
}
void upd(int s, int e, pii x, int l=0, int r=n, int id=1) {
    if(s>=r || l>=e) return;
    if(s<=l && r<=e) {
        apply(x, id);
        return;
    }
    push(id);
    upd(s, e, x, l, mid, lc);
    upd(s, e, x, mid, r, rc);
}
void print(int ans[], int l=0, int r=n, int id=1) {
    if(r-l == 1) {
        ans[l] = lz[id].X;
        return;
    }
    push(id);
    print(ans, l, mid, lc);
    print(ans, mid, r, rc);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    ::n = n;
    build();
    for(int i=0; i<k; i++)
        if(op[i] == 1) 
            upd(left[i], right[i]+1, {height[i], 100001});
        else
            upd(left[i], right[i]+1, {-1, height[i]+1});
    print(finalHeight);
}

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