Submission #1092876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092876		daviedu	Wall (IOI14_wall)	C++17	100 / 100	599 ms	75688 KiB

wall

#include <bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int) (a).size()
#define ll long long
#define ld long double
#define pb push_back

struct P{
    ll x, y;
};

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

#define bound array<int, 2>

const bound neutral = {0, INT_MAX};
const bound no_lazy = {-1, -1};
const int MI = 0, MA = INT_MAX;

class Segtree{
public:
    int n;
    vector<int> t, hi, lo; // lazy is not a bound, but an operation with 2 parameters
    Segtree(int size){
        n = 1;
        while (n < size) n <<= 1;
        t.resize(2*n);
        hi.resize(2*n, MA);
        lo.resize(2*n, MI);
    }
    void apply(int i){
        t[i] = max(t[i], lo[i]);
        t[i] = min(t[i], hi[i]);
        hi[i] = MA;
        lo[i] = MI;
    }

    void comb(int down, int i){
        if (hi[down] <= lo[i]) lo[down] = hi[down] = lo[i];
        if (lo[down] >= hi[i]) lo[down] = hi[down] = hi[i];
        else{
            lo[down] = max(lo[down], lo[i]);
            hi[down] = min(hi[down], hi[i]);
        }
    }

    void prop(int i){
        if (lo[i] == MI && hi[i] == MA) return;
        if (i >= n) apply(i);
        else{
            comb(2*i, i);
            comb(2*i+1, i);
            hi[i] = MA;
            lo[i] = MI;
        }
    }
    void update(int l, int r, int i, int a, int b, int v, int op){
        prop(i);
        if (b < l || r < a) return;
        if (a <= l && r <= b){
            if (op == 1) lo[i] = v;
            else hi[i] = v;
            prop(i);
            return;
        }
        int m = (l+r)/2;
        update(l, m, 2*i, a, b, v, op);
        update(m+1, r, 2*i+1, a, b, v, op);
    }
    void update(int l, int r, int v, int op){
        update(0, n-1, 1, l, r, v, op);
    }

    int query(int l, int r, int i, int pos){
        prop(i);
        assert(lo[i] == MI && hi[i] == MA);
        if (l == r && l == pos) return t[i];
        int m = (l+r)/2;
        if (pos <= m) return query(l, m, 2*i, pos);
        else return query(m+1, r, 2*i+1, pos);
    }
    int query(int pos){
        return query(0, n-1, 1, pos);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    Segtree seg (n);
    for (int i=0; i<k; i++){
        seg.update(left[i], right[i], height[i], op[i]);
    }
    for (int i=0; i<n; i++){
        finalHeight[i] = seg.query(i);
    }
}

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