Submission #691700

#	Time	Username	Problem	Language	Result	Execution time	Memory
691700		ismayil	Wall (IOI14_wall)	C++17	0 / 100	1 ms	340 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
using namespace std;
const int INF = 2e9;
struct segtree{
    struct node{
        int mn, mx;
    };
    vector<node> tree;
    int size;
    segtree(int n){
        size = 1;
        while(size < n) size *= 2;
        tree.resize(2 * size - 1, {0, INF});
    }
    void propagate(int x, int lx, int rx){
        tree[2 * x + 1].mn = min(tree[2 * x + 1].mn, tree[x].mn);
        tree[2 * x + 1].mn = max(tree[2 * x + 1].mn, tree[x].mx);
        tree[2 * x + 1].mx = min(tree[2 * x + 1].mx, tree[x].mn);
        tree[2 * x + 1].mx = max(tree[2 * x + 1].mx, tree[x].mx);

        tree[2 * x + 2].mn = min(tree[2 * x + 2].mn, tree[x].mn);
        tree[2 * x + 2].mn = max(tree[2 * x + 2].mn, tree[x].mx);
        tree[2 * x + 2].mx = min(tree[2 * x + 2].mx, tree[x].mn);
        tree[2 * x + 2].mx = max(tree[2 * x + 2].mx, tree[x].mx);

        tree[x].mn = 0;
        tree[x].mx = INF;
    }
    void update(int op, int l, int r, int h, int x, int lx, int rx){
        if(r <= lx || rx <= l) return;
        if(l <= lx && rx <= r){
            if(op == 1){
                tree[x].mn = max(tree[x].mn, h);
                tree[x].mx = max(tree[x].mx, h);
            }else{
                tree[x].mn = min(tree[x].mn, h);
                tree[x].mx = min(tree[x].mx, h);
            }
        }
        propagate(x, lx, rx);
        int mx = (lx + rx) / 2;
        update(op, l, r, h, 2 * x + 1, lx, mx);
        update(op, l, r, h, 2 * x + 2, mx, rx);
    }
    void update(int op, int l, int r, int h){
        update(op, l, r, h, 0, 0, size);
    }
    int query(int pos, int x, int lx, int rx){
        if(rx - lx == 1){
            return tree[x].mn;
        }
        propagate(x, lx, rx);
        int mx = (lx + rx) / 2;
        if(pos <= mx) return query(pos, 2 * x + 1, lx, mx);
        return query(pos, 2 * x + 2, mx, rx);
    }
    int query(int pos){
        return query(pos, 0, 0, size);
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    segtree st(n);
    for (int i = 0; i < k; i++) st.update(op[i], left[i], right[i] + 1, height[i]);
    for (int i = 0; i < n; i++) finalHeight[i] = st.query(i);
}

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