Submission #1191300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191300		LolkasMeep	Wall (IOI14_wall)	C++20	61 / 100	727 ms	276640 KiB

wall

#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;

struct SeggsTree{
    SeggsTree *l = 0, *r = 0;
    int low = 0, high = 0;
    
    struct Data{
        ll mx, mn;
        Data() {mx = -(INT_MAX-1), mn = INT_MAX;}
        Data(ll X, ll N) {mx = X, mn = N;}

        static Data merge(Data a, Data b){
            return Data(max(a.mx, b.mx), min(a.mn, b.mn));
        }
    };

    Data d;

    SeggsTree(int L, int R){
        low = L, high = R;
        if(R - L <= 1){
            d = Data(0, 0);
            return;
        }

        int mid = low + (high - low) / 2;

        l = new SeggsTree(low, mid);
        r = new SeggsTree(mid, high);
        d = Data::merge(l->d, r->d);
    }

    ~SeggsTree(){
        if(!l) return;
        delete l;
        delete r;
    }

    int lazy = -1;

    void push(){
        if(lazy == -1) return;
        l->d = Data(lazy, lazy);
        l->lazy = lazy;
        r->d = Data(lazy, lazy);
        r->lazy = lazy;
        lazy = -1;
    }

    Data query(int L, int R){
        if(R <= low || high <= L) return Data();
        if(L <= low && high <= R) return d;
        push();

        return Data::merge(l->query(L,R), r->query(L, R));
    }

    void updateAdd(int L, int R, int k){
        if(R <= low || high <= L || d.mn >= k) return;
        if(L <= low && high <= R && d.mx <= k){
            d = Data(k, k);
            lazy = k;
            return;
        }
        push();
        l->updateAdd(L, R, k);
        r->updateAdd(L, R, k);
        d = Data::merge(l->d, r->d);
    }

    void updateSub(int L, int R, int k){
        if(R <= low || high <= L || d.mx <= k) return;
        if(L <= low && high <= R && d.mn >= k){
            d = Data(k, k);
            lazy = k;
            return;
        }
        push();
        l->updateSub(L, R, k);
        r->updateSub(L, R, k);
        d = Data::merge(l->d, r->d);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[],
    int height[], int finalHeight[]){
    SeggsTree *tree = new SeggsTree(0, n);
    for(int i = 0; i < k; i++){
        if(op[i] == 1) tree->updateAdd(left[i], right[i]+1, height[i]);
        else tree->updateSub(left[i], right[i]+1, height[i]);
    }

    for(int i = 0; i < n; i++) finalHeight[i] = tree->query(i, i+1).mn;
}

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