Submission #1098832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098832		Zero_OP	Wall (IOI14_wall)	C++14	100 / 100	799 ms	89288 KiB

wall

#include "bits/stdc++.h"
#ifndef LOCAL
#include "wall.h"
#endif

using namespace std;

struct item{
    int l, r;
    item(int l = 0, int r = INT_MAX) : l(l), r(r) {}
};

struct SegmentTree{
    vector<item> st;
    SegmentTree(int n) : st(n << 2) {}

    void apply(int id, const item& val){
        st[id].l = max(st[id].l, val.l);
        st[id].l = min(st[id].l, val.r);
        st[id].r = max(st[id].r, val.l);
        st[id].r = min(st[id].r, val.r);
    }

    void lazyDown(int id){
        apply(id << 1, st[id]);
        apply(id << 1 | 1, st[id]);
        st[id] = item();
    }

    void update(int id, int l, int r, int u, int v, const item& val){
        if(u <= l && r <= v){
            apply(id, val);
        } else{
            int mid = l + r >> 1;
            lazyDown(id);

            if(u <= mid) update(id << 1, l, mid, u, v, val);
            if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, val);
        }
    }

    item query(int id, int l, int r, int k){
        if(l == r) return st[id];
        int mid = l + r >> 1;
        lazyDown(id);

        if(k <= mid) return query(id << 1, l, mid, k);
        else return query(id << 1 | 1, mid + 1, r, k);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SegmentTree T(n);
    for(int i = 0; i < k; ++i){
        if(op[i] == 1){
            T.update(1, 0, n - 1, left[i], right[i], {height[i], INT_MAX});
        } else{
            T.update(1, 0, n - 1, left[i], right[i], {0, height[i]});
        }
    }

    for(int i = 0; i < n; ++i){
        finalHeight[i] = T.query(1, 0, n - 1, i).l;
    }
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n = 10, k = 6;
    int op[] = {1, 2, 2, 1, 1, 2}, left[] = {1, 4, 3, 0, 2, 6}, right[] = {8, 9, 6, 5, 2, 7}, height[] = {4, 1, 5, 3, 5, 0};
    int finalHeight[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

    buildWall(n, k, op, left, right, height, finalHeight);
    for(int i = 0; i < n; ++i){
        cout << finalHeight[i] << ' ';
    }
    cout << '\n';

    return 0;
}
#endif

Compilation message (stderr)

wall.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, const item&)':
wall.cpp:34:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |             int mid = l + r >> 1;
      |                       ~~^~~
wall.cpp: In member function 'item SegmentTree::query(int, int, int, int)':
wall.cpp:44:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mid = l + r >> 1;
      |                   ~~^~~

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