Submission #1186102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186102		harvsftw	Wall (IOI14_wall)	C++20	100 / 100	381 ms	40272 KiB

wall

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

#define F(i, n) for(int i = 0; i < (n); i++)
using pii = pair<int, int>;
pii merge(pii a, pii b) {
    if(a.second < b.first) {
        return {b.first, b.first};
    } else if(b.second < a.first) {
        return {b.second, b.second};
    } else {
        return {max(a.first, b.first), min(a.second, b.second)};
    }
}

struct segtree {
    pii segtree[1 << 21];
    int segtree_size = 1;

    pii zero = {0, INT_MAX};
    void init(int n) {
        segtree_size = 1;
        while(segtree_size < n) {
            segtree_size <<= 1;
        }
        F(i, 2 * segtree_size) {
            segtree[i] = zero;
        }
    }
    pii add(pii a, pii b) {
        return merge(a, b);
    }
 
    pii get(int i, int window_l, int window_r, int l, int r) {
        if(l <= window_l && window_r <= r) {
            return segtree[i];
        } else if(window_l <= l && l <= window_r || window_l <= r && r <= window_r) {
            int m = (window_l + window_r) / 2;
            return add(get(i * 2 + 0, window_l,m,l,r), get(i * 2 + 1,m + 1,window_r,l,r));
        } else {
            return zero;
        }
    }
 
    pii get(int l, int r) {
        if(l > r) {
            return zero;
        }
        return get(1, 0, segtree_size - 1, l, r);
    }
 
    void set(int i, pii data) {
        i += segtree_size;
        segtree[i] = data;
        i /= 2;
        while(i > 0) {
            segtree[i] = add(segtree[i * 2 + 0], segtree[i * 2 + 1]);
            i /= 2;
        }
    }
} ohio;

enum evt_type {
    ENTRY,
    EXIT
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    vector<pair<int, int>> intervals;
    vector<tuple<int, evt_type, int>> evts;
    ohio.init(k);
    F(i, k) {
        if(op[i] == 1) {
            intervals.emplace_back(height[i], INT_MAX);
        } else if(op[i] == 2) {
            intervals.emplace_back(0, height[i]);
        } else {
            assert(false);
        }

        evts.emplace_back(left[i], ENTRY, i);
        evts.emplace_back(right[i] + 1, EXIT, i);
    }

    sort(evts.begin(), evts.end());
    
    auto it = evts.begin();
    F(i, n) {
        while(it != evts.end() && get<0>(*it) == i) {
            auto [wall_idx, evt_type, interval_idx] = *it;
            if(evt_type == ENTRY) {
                ohio.set(interval_idx, intervals[interval_idx]);
            } else {
                ohio.set(interval_idx, ohio.zero);
            }
            ++it;
        }

        finalHeight[i] = merge({0, 0}, ohio.segtree[1]).first;
    }
}

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