Submission #717526

#	Time	Username	Problem	Language	Result	Execution time	Memory
717526		walterw	Two Antennas (JOI19_antennas)	C++17	100 / 100	599 ms	69476 KiB

antennas

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

#define int ll

int H[200005], A[200005], B[200005];

struct event {
    int time, idx, height; bool add;

    bool operator<(event o) const {

        return time < o.time;
    }
};

vector<event> events;

pair<int, int> vals[4 * 200005];
int ans[4 * 200005];
pair<int, int> qs[4 * 200005];
const pair<int, int> null = {1e16, 0};

void build() {
    fill(ans, ans+ 4 * 200005, -1);
    for (int i = 1; i < 4 * 200005; i++) {
        vals[i] = qs[i] = null;
    }
}

pair<int, int> comb(pair<int, int> a, pair<int, int> b) {
    return {min(a.first, b.first), max(a.second, b.second)};
}

int eval(pair<int, int> vals, pair<int, int> qs) {
    int res = - 1;

    if (qs.first < (ll) 1e16) {
        if (vals.first < (ll) 1e16) res = max(res, abs(qs.first - vals.first));
        if (vals.second > 0) res = max(res, abs(qs.first - vals.second));
    }
    if (qs.second > 0) {
        if (vals.first < (ll) 1e16) res = max(res, abs(qs.second - vals.first));
        if (vals.second > 0) res = max(res, abs(qs.second - vals.second));
    }

    return res;
}

void push(int x) {
    if (qs[x] != null) {
        ans[2 * x] = max(ans[2 * x], eval(vals[2 * x], qs[x]));
        qs[2 * x] = comb(qs[2 * x], qs[x]);

        ans[2 * x + 1] = max(ans[2 * x + 1], eval(vals[2 * x + 1], qs[x]));
        qs[2 * x + 1] = comb(qs[2 * x + 1], qs[x]);

        qs[x] = null;
    }
}

void update(int x, int l, int r, int idx, int h) {
    if (l == r) {
        if (h) vals[x] = {h, h};
        else vals[x] = null;
        return;
    }

    push(x);
    int mid = (l + r) / 2;
    if (idx <= mid) update(2 * x, l, mid, idx, h);
    else update(2 * x + 1, mid + 1, r, idx, h);

    vals[x] = comb(vals[2 * x], vals[2 * x + 1]);
    ans[x] = max(ans[2 * x], ans[2 * x + 1]);
}

void updatequery(int x, int l, int r, int ql, int qr, int curh) {
    if (ql <= l && r <= qr) {
        // fully within
        ans[x] = max(ans[x], eval(vals[x], {curh, curh}));
        qs[x] = comb(qs[x], {curh, curh});
        return;
    }

    if (l > qr || ql > r) return;

    int mid = (l + r) / 2;
    push(x);

    updatequery(2 * x, l, mid, ql, qr , curh);
    updatequery(2 * x + 1, mid + 1, r, ql, qr, curh);

    vals[x] = comb(vals[2 * x], vals[2 * x + 1]);
    ans[x] = max(ans[2 * x], ans[2 * x + 1]);
}

int query(int x, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return ans[x];
    if (l > qr || ql > r) return -1;

    int mid = (l + r) / 2;
    push(x);

    int ans1 = query(2 * x, l, mid, ql, qr);
    int ans2 = query(2 * x + 1, mid + 1, r, ql, qr);

    vals[x] = comb(vals[2 * x], vals[2 * x + 1]);
    ans[x] = max(ans[2 * x], ans[2 * x + 1]);

    return max(ans1, ans2);
}


vector<pair<int, int>> queries[200005];
int toprint[200005];

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> H[i] >> A[i] >> B[i];
    }

    int q; cin >> q;
    for (int i = 1; i <= q; i++) {
        int a, b; cin >> a >> b;
        queries[b].emplace_back(a, i);
    }

    for (int i = 1; i <= n; i++) {
        events.push_back({i + A[i], i,  H[i], true});
        events.push_back({i + B[i] + 1, i, H[i], false});
    }

    sort(events.begin(), events.end());
    int idx = 0;

    build();

    for (int i = 1; i <= n; i++) {
        while (idx < events.size() && events[idx].time == i) {
            if (events[idx].add) {
                update(1, 1, n, events[idx].idx, events[idx].height);
            } else {
                update(1, 1, n, events[idx].idx, 0);
            }

            idx++;
        }

        if (i - A[i] >= 1) updatequery(1, 1, n, max((ll) 1, i - B[i]), max((ll) 1, i - A[i]), H[i]);

        for (auto [l, id] : queries[i]) {
            toprint[id] = query(1, 1, n, l, i);
        }
    }

    for (int i = 1; i <= q; i++) {
        cout << toprint[i] << "\n";
    }

}

Compilation message (stderr)

antennas.cpp: In function 'int32_t main()':
antennas.cpp:173:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |         while (idx < events.size() && events[idx].time == i) {
      |                ~~~~^~~~~~~~~~~~~~~

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