Submission #151964

#	Time	Username	Problem	Language	Result	Execution time	Memory
151964		erebos	Wall (IOI14_wall)	C++17	0 / 100	235 ms	13944 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int inf = 1e9;
struct wall {
    int mn=0, mx=0;
};
wall operator+(wall a, wall b) {
    return {min({max({a.mn, b.mn}), b.mx}), min({max({a.mx, b.mn}), b.mx})};
}
vector<wall>tree;
void update(int node, int s, int e, int l, int r, wall diff) {
    if(e<l || r<s) return;
    if(s!=e) {
        tree[node*2]=tree[node*2]+tree[node];
        tree[node*2+1]=tree[node*2+1]+tree[node];
        tree[node]= {0, inf};
    }
    if(l<=s && e<=r) {
        tree[node]=tree[node]+diff;
    } else {
        update(node*2, s, (s+e)/2, l, r, diff);
        update(node*2+1, (s+e)/2+1, e, l, r, diff);
    }
}
wall query(int node, int s, int e, int num) {
    if(e<num || num<s) return{0, inf};
    if(s==e) return tree[node];
    return query(node*2, s, (s+e)/2, num)+query(node*2+1, (s+e)/2+1, e, num)+tree[node];
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    int h=(int)ceil(log2(n));
    int tree_size=1<<(h+1);
    tree.resize(tree_size);
    for(int i=0; i<k; ++i) {
        if(op[i]==1) { //+
            update(1, 1, n, left[i]+1, right[i]+1, {height[i], inf});
        } else { //-
            update(1, 1, n, left[i+1], right[i]+1, {0, height[i]});
        }
    }
    for(int i=0; i<n; ++i) {
        finalHeight[i]=query(1, 1, n, i+1).mx;
    }
}

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