Submission #581419

#	Time	Username	Problem	Language	Result	Execution time	Memory
581419		Josia	Wall (IOI14_wall)	C++14	100 / 100	1857 ms	48088 KiB

wall

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



struct segtree {
    struct node {
        int Max;
        int Min;

        node() {
            Max = 1e9;
            Min = -1e9;
        }
    };
    vector<node> tree;

    node op(node a, node b) {
        node res;
        res.Min = max(a.Min, b.Min);
        res.Max = min(a.Max, b.Max);
        if (res.Min > res.Max) {
            if (b.Min > a.Max) {
                res.Max = b.Min;
            }
            if (b.Max < a.Min) {
                res.Min = b.Max;
            }
        }
        return res;
    }


    node queryAll() {
        return tree[1];
    }

    void update(int v, int rl, int rr, int pos, node x) {
        if (rl == rr) {
            tree[v] = x; return;
        }
        int rm = (rl + rr) / 2;
        if (pos <= rm) update(v*2, rl, rm, pos, x);
        else update(v*2+1, rm+1, rr, pos, x);

        tree[v] = op(tree[v*2], tree[v*2+1]);
    }
};



struct event {
    int t;
    int index;
    int x;
    bool start; // 1start; 0end
    bool type;  // 1max; 0min
};
bool compare(event a, event b) {
    return vector<int>{a.t, a.index, a.x, a.start, a.type} < vector<int>{b.t, b.index, b.x, b.start, b.type};
}




void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    deque<event> events;
    for (int i=0; i<k; i++) {
        event blub;
        blub.index = i;
        blub.x = height[i];
        blub.type = op[i]-1;
        blub.t = left[i];
        blub.start = 1;
        events.push_back(blub);
        blub.t = right[i]+1;
        blub.start = 0;
        events.push_back(blub);
    }

    sort(events.begin(), events.end(), compare);

    segtree seg;

    seg.tree.assign(k*4, segtree::node());


    for (int i = 0; i<n; i++) {
        while (events[0].t == i) {
            if (events[0].start == 0) {
                seg.update(1, 0, k-1, events[0].index, segtree::node());
            }

            else {
                segtree::node newOp;
                if (events[0].type) {newOp.Max = events[0].x; newOp.Min = -1e9;}
                else {newOp.Min = events[0].x; newOp.Max = 1e9;}
                seg.update(1, 0, k-1, events[0].index, newOp);
            }

            events.pop_front();
        }

        finalHeight[i] = max(0, seg.queryAll().Min);
    }

    return;
}

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