Submission #1103960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103960		_callmelucian	Two Antennas (JOI19_antennas)	C++14	100 / 100	628 ms	49484 KiB

antennas

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct IT {
    vector<int> minA, maxA, minB, maxB, best;
    IT (int sz) : minA(4 * sz, INT_MAX), maxA(4 * sz, INT_MIN),
                  minB(4 * sz, INT_MAX), maxB(4 * sz, INT_MIN), best(4 * sz, INT_MIN) {}

    void applyA (int k, int minVal, int maxVal) {
        minB[k] = INT_MAX, maxB[k] = INT_MIN;
        minA[k] = minVal, maxA[k] = maxVal;
    }

    void applyB (int k, int minVal, int maxVal) {
        minB[k] = min(minB[k], minVal);
        maxB[k] = max(maxB[k], maxVal);
        if (maxA[k] != INT_MIN && minB[k] != INT_MAX)
            best[k] = max(best[k], maxA[k] - minB[k]);
        if (maxB[k] != INT_MIN && minA[k] != INT_MAX)
            best[k] = max(best[k], maxB[k] - minA[k]);
    }

    void pullUp (int k) {
        best[k] = max(best[2 * k], best[2 * k + 1]);
        minA[k] = min(minA[2 * k], minA[2 * k + 1]);
        maxA[k] = max(maxA[2 * k], maxA[2 * k + 1]);
    }

    void pushDown (int k) {
        applyB(2 * k, minB[k], maxB[k]), applyB(2 * k + 1, minB[k], maxB[k]);
        minB[k] = INT_MAX, maxB[k] = INT_MIN;
        pullUp(k);
    }

    void insertPoint (int pos, int minVal, int maxVal, int k, int l, int r) {
        if (pos < l || r < pos) return;
        if (l == r) return applyA(k, minVal, maxVal), void();
        pushDown(k);
        int mid = (l + r) >> 1;
        insertPoint(pos, minVal, maxVal, 2 * k, l, mid);
        insertPoint(pos, minVal, maxVal, 2 * k + 1, mid + 1, r);
        pullUp(k);
    }

    void applyRange (int a, int b, int val, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) return applyB(k, val, val), void();
        pushDown(k);
        int mid = (l + r) >> 1;
        applyRange(a, b, val, 2 * k, l, mid);
        applyRange(a, b, val, 2 * k + 1, mid + 1, r);
        pullUp(k);
    }

    int query (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return INT_MIN;
        if (a <= l && r <= b) return best[k];
        pushDown(k);
        int mid = (l + r) >> 1;
        return max(query(a, b, 2 * k, l, mid),
                   query(a, b, 2 * k + 1, mid + 1, r));
    }
};

const int mn = 2e5 + 5;
vector<int> open[mn], close[mn];
vector<pii> qry[mn];
int h[mn], a[mn], b[mn], ans[mn];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> a[i] >> b[i];
        if (i + a[i] <= n) open[i + a[i]].push_back(i);
        if (i + b[i] <= n) close[i + b[i]].push_back(i);
    }

    int q; cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;
        qry[r].emplace_back(l, i);
    }

    IT tree(n);
    for (int i = 1; i <= n; i++) {
        for (int u : open[i])
            tree.insertPoint(u, h[u], h[u], 1, 1, n);
        if (1 <= i - a[i])
            tree.applyRange(max(1, i - b[i]), i - a[i], h[i], 1, 1, n);

        for (pii it : qry[i]) {
            int l, idx; tie(l, idx) = it;
            ans[idx] = tree.query(l, i, 1, 1, n);
        }
        for (int u : close[i])
            tree.insertPoint(u, INT_MAX, INT_MIN, 1, 1, n);
    }

    for (int i = 0; i < q; i++)
        cout << (ans[i] == INT_MIN ? -1 : ans[i]) << "\n";

    return 0;
}

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