Submission #199645

#	Time	Username	Problem	Language	Result	Execution time	Memory
199645		popovicirobert	Two Antennas (JOI19_antennas)	C++14	100 / 100	1276 ms	40808 KiB

antennas

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define uint unsigned int


using namespace std;

const int INF = 1e9;

struct Query {
    int l, pos;
};

vector <int> h, a, b;
vector <int> l, r;
vector <int> sol;

struct Event {
    int x, type, pos;
    bool operator <(const Event &other) const {
        if(x == other.x) return type < other.type;
        return x < other.x;
    }
};

struct Node {
    int val, mx, lazy;
    Node(int _val = INF, int _mx = -INF, int _lazy = -INF) : val(_val), mx(_mx), lazy(_lazy) {}
};

struct SegTree {
    vector <Node> aint;
    int n, sz;

    SegTree(int _n) {
        n = _n, sz = 1;
        while(sz < 2 * n) {
            sz *= 2;
        }
        aint.resize(sz + 1);
    }

    inline void push(int nod) {
        if(2 * nod + 1 <= sz) {
            aint[2 * nod].lazy = max(aint[2 * nod].lazy, aint[nod].lazy);
            aint[2 * nod + 1].lazy = max(aint[2 * nod + 1].lazy, aint[nod].lazy);
        }
        aint[nod].mx = max(aint[nod].mx, aint[nod].lazy - aint[nod].val);
        aint[nod].lazy = -INF;
    }

    inline void combine(Node a, Node b, Node &ans) {
        ans.val = min(a.val, b.val);
        ans.mx = max(ans.mx, max(a.mx, b.mx));
    }

    void update(int nod, int left, int right, int pos, int val) {
        push(nod);

        if(left == right) {
            aint[nod].val = val;
        }
        else {
            int mid = (left + right) / 2;

            if(pos <= mid) update(2 * nod, left, mid, pos, val);
            else update(2 * nod + 1, mid + 1, right, pos, val);

            combine(aint[2 * nod], aint[2 * nod + 1], aint[nod]);
        }
    }

    void update(int nod, int left, int right, int l, int r, int lazy) {
        push(nod);

        if(l > right || r < left || l > r) return ;

        if(l <= left && right <= r) {
            aint[nod].lazy = max(aint[nod].lazy, lazy);
            push(nod);
            return ;
        }

        int mid = (left + right) / 2;

        update(2 * nod, left, mid, l, r, lazy);
        update(2 * nod + 1, mid + 1, right, l, r, lazy);

        combine(aint[2 * nod], aint[2 * nod + 1], aint[nod]);
    }

    int query(int nod, int left, int right, int l, int r) {
        push(nod);

        if(l > right || r < left || l > r) return -INF;

        if(l <= left && right <= r) {
            return aint[nod].mx;
        }

        int mid = (left + right) / 2;
        int ans = max(query(2 * nod, left, mid, l, r), query(2 * nod + 1, mid + 1, right, l, r));

        combine(aint[2 * nod], aint[2 * nod + 1], aint[nod]);

        return ans;
    }
};

inline void solve(int n, int q) {
    vector < vector <Query> > qry(n + 1);
    int i;
    for(i = 1; i <= q; i++) {
        qry[r[i]].push_back({l[i], i});
    }

    vector <Event> evs;
    for(i = 1; i <= n; i++) {
        evs.push_back({i + a[i], -1, i});
        evs.push_back({i + b[i] + 1, 0, i});
        evs.push_back({i, 1, i});
    }
    sort(evs.begin(), evs.end());

    SegTree st(n);
    i = 0;

    while(i < 3 * n) {
        int j = i;
        while(j < 3 * n && evs[i].x == evs[j].x) {
            //cerr << evs[j].x << " " << evs[j].pos << " " << evs[j].type << "\n";
            if(evs[j].type == -1) {
                st.update(1, 1, n, evs[j].pos, h[evs[j].pos]);
            }
            if(evs[j].type == 0) {
                st.update(1, 1, n, evs[j].pos, INF);
            }
            if(evs[j].type == 1) {
                //cerr << evs[j].pos << " " << max(1, evs[j].pos - b[evs[j].pos]) << " " << min(n, evs[j].pos - a[evs[j].pos]) << "\n";
                st.update(1, 1, n, max(1, evs[j].pos - b[evs[j].pos]), min(n, evs[j].pos - a[evs[j].pos]), h[evs[j].pos]);
                //cerr << evs[j].pos << " " << evs[j].type << "\n";
                //cerr << st.query(1, 1, n, 1, evs[j].x) << " " << max(1, evs[j].pos - b[evs[j].pos]) << " " << min(n, evs[j].pos - a[evs[j].pos]) << "\n";
            }
            j++;
        }

        if(evs[i].x >= 1 && evs[i].x <= n) {
            for(auto it : qry[evs[i].x]) {
                int cur = st.query(1, 1, n, it.l, evs[i].x);
                sol[it.pos] = max(sol[it.pos], cur);
            }
        }

        i = j;
    }
}

int main() {
#ifdef HOME
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, n, q;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    h.resize(n + 1), a.resize(n + 1), b.resize(n + 1);
    for(i = 1; i <= n; i++) {
        cin >> h[i] >> a[i] >> b[i];
    }

    cin >> q;
    l.resize(q + 1), r.resize(q + 1);
    for(i = 1; i <= q; i++) {
        cin >> l[i] >> r[i];
    }

    sol.resize(q + 1, -1);

    solve(n, q);

    for(i = 1; i < n - i + 1; i++) {
        swap(h[i], h[n - i + 1]);
        swap(a[i], a[n - i + 1]);
        swap(b[i], b[n - i + 1]);
    }
    for(i = 1; i <= q; i++) {
        l[i] = n - l[i] + 1;
        r[i] = n - r[i] + 1;
        swap(l[i], r[i]);
    }

    solve(n, q);

    for(i = 1; i <= q; i++) {
        cout << max(sol[i], -1) << "\n";
    }

    return 0;
}

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