Submission #1308327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308327		888313666	Wall (IOI14_wall)	C++20	24 / 100	621 ms	16348 KiB

wall

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef array<int, 2> ii;
constexpr int inf=INT_MAX>>2;
constexpr array<int, 2> id={-inf, inf};

void apply(array<int, 2> &a, const array<int, 2> &b, const int op){
    a[0]=max(a[0], b[0]);
    a[1]=min(a[1], b[1]);
    if (a[0]>a[1]){
        if (!op){
            a[0]=a[1]=b[1];
        } else {
            a[0]=a[1]=b[0];
        }
    }
}

struct segtree{
    vector<array<int, 2>> st, lz;
    vector<int> op;
    int n;
    
    void build(const int l, const int r, const int i){
        if (l+1==r) st[i]={0,0};
        else {
            const auto m=l+(r-l>>1);
            build(l, m, (i<<1)+1);
            build(m, r, (i<<1)+2);
        }
    }

    segtree(const int n){
        this->n=n;
        st.assign(n<<2, id);
        lz.assign(n<<2, id);
        op.assign(n<<2, 0);
        build(0, n, 0);
    }

    void propagate(const int l, const int r, const int i){
        if (lz[i]==id) return;
        apply(st[i], lz[i], op[i]);
        if (l+1!=r){
            apply(lz[(i<<1)+1], lz[i], op[i]);
            apply(lz[(i<<1)+2], lz[i], op[i]);
            op[(i<<1)+1]=op[(i<<1)+2]=op[i];
        }
        op[i]=0;
        lz[i]=id;
    }

    void upd(const int l, const int r, const int cl, const int cr, const int i, const ii d, const int o){
        propagate(cl, cr, i);
        if (cr<=l || r<=cl || cr<=cl) return;
        if (l<=cl && cr<=r){
            apply(st[i], d, o);
            if (cl+1!=cr){
                apply(lz[(i<<1)+1], d, o);
                apply(lz[(i<<1)+2], d, o);
                op[(i<<1)+1]=op[(i<<1)+2]=o;
            }
            return;
        }
        const auto m=cl+(cr-cl>>1);
        upd(l, r, cl, m, (i<<1)+1, d, o);
        upd(l, r, m, cr, (i<<1)+2, d, o);
    }

    void update(const int l, const int r, const int d, const int o){
        if (o) upd(l, r, 0, n, 0, {d, inf}, o);
        else upd(l, r, 0, n, 0, {-inf, d}, o);
    }

    ii qry(const int tg, const int cl, const int cr, const int i){
        propagate(cl, cr, i);
        if (cr<=tg || tg<cl || cr<=cl) return id;
        if (cl+1==cr){
            return st[i];
        }
        const auto m=cl+(cr-cl>>1);
        const auto res=qry(tg, cl, m, (i<<1)+1);
        if (res!=id) return res;
        return qry(tg, m, cr, (i<<1)+2);
    }

    ii query(const int p){ // pt qry
        return qry(p, 0, n, 0);
    }

};

void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]){
    segtree f(n);
    for (int i=0; i<k; i++){
        if (op[i]==2){
            f.update(left[i], right[i]+1, height[i], 0);
        }else {
            f.update(left[i], right[i]+1, height[i], 1);
        }
    }
    for (int i=0; i<n; i++){
        finalHeight[i]=f.query(i)[0];
    }
}

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