Submission #796501

#	Time	Username	Problem	Language	Result	Execution time	Memory
796501		thimote75	Two Antennas (JOI19_antennas)	C++14	24 / 100	3057 ms	21228 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using bdata = vector<bool>;

const int START = 0;
const int END   = 1;
const int QUERY = 2;

struct Event {
    int pos, type, id;

    Event (int pos, int type, int id) : pos(pos), type(type), id(id) {}

    bool operator< (const Event &other) const {
        if (pos == other.pos) return type < other.type;
        return pos < other.pos;
    }
};
using vEvent = vector<Event>;

struct SGData {
    bool enabled = false;
    int mx = -1; int mn = -1;

    void merge (SGData &left, SGData &right) {
        enabled = left.enabled | right.enabled;

        if (!left.enabled) {
            mx = right.mx;
            mn = right.mn;
        } else if (!right.enabled) {
            mx = left.mx;
            mn = left.mn;
        } else {
            mx = max(left.mx, right.mx);
            mn = min(left.mn, right.mn);
        }
    }
};

struct SegTree {
    vector<SGData> tree;

    int size, start, height;

    SegTree (idata heights) {
        size = heights.size();

        height = ceil(log2(size));
        start = 1 << height;

        tree.resize(start << 1);

        for (int i = 0; i < size; i ++) {
            tree[i + start].mx = heights[i];
            tree[i + start].mn = heights[i];
        }
    }
    void toggle (int index) {
        index += start;
        tree[index].enabled = !tree[index].enabled;

        index >>= 1;
        while (index != 0) {
            tree[index].merge(tree[index * 2], tree[index * 2 + 1]);

            index >>= 1;
        }
    }
    SGData query (int l, int r) {
        l += start;
        r += start;

        SGData local;
        SGData result;
        while (l < r) {
            if ((l & 1) == 1) { local.merge(result, tree[l]); result = local; }
            if ((r & 1) == 0) { local.merge(result, tree[r]); result = local; }
        
            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }

        if (l == r) { local.merge(result, tree[l]); result = local; }

        return result;
    }
};

vEvent events;

idata heights;
idata left_q;
idata right_q;

bdata enabled;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    heights.resize(N);
    left_q .resize(N);
    right_q.resize(N);
    for (int i = 0; i < N; i ++) {
        int h, a, b;
        cin >> h >> a >> b;

        heights[i] = h;
        left_q [i] = i + a;
        right_q[i] = i + b;

        events.push_back(Event( i - b,     START, i ));
        events.push_back(Event( i - a + 1, END,   i ));
        events.push_back(Event( i, QUERY, i ));
    }

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

    int Q; cin >> Q;
    enabled.resize(N);

    SegTree tree(heights);

    for (int q = 0; q < Q; q ++) {
        int l, r;
        cin >> l >> r;
        l --; r --;

        int res = -1;
        for (Event &event : events) {
            if (event.type == START) {
                tree.toggle(event.id);
            } else if (event.type == END) {
                tree.toggle(event.id);
            } else {
                if (event.id < l) continue ;
                if (event.id > r) continue ;

                if (left_q[event.id] > r) continue ;
                SGData data = tree.query(left_q[event.id], min(r, right_q[event.id]));

                if (!data.enabled) continue ;
                res = max(res, data.mx - heights[event.id]);
                res = max(res, heights[event.id] - data.mn);
            }
        }

        cout << res << "\n";
    }
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65