Submission #1170305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170305		patgra	Two Antennas (JOI19_antennas)	C++20	35 / 100	848 ms	192388 KiB

antennas

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

constexpr int maxLog = 12;

constexpr int tb = 1 << 19;
pair<ll, ll> t[2 * tb];
void ts(int i, pair<ll, ll> x) {
    i += tb;
    t[i] = x;
    while(i) i /= 2, t[i] = {max(t[2 * i].first, t[2 * i + 1].first), min(t[2 * i].second, t[2 * i + 1].second)};
}
void ts(int i, ll x) {
    i += tb;
    t[i] = {x, x};
    while(i) i /= 2, t[i] = {max(t[2 * i].first, t[2 * i + 1].first), min(t[2 * i].second, t[2 * i + 1].second)};
}
pair<ll, ll> tq(int l, int r) {
    l += tb;
    r += tb;
    ll mx = max(t[l].first, t[r].first);
    ll mn = min(t[l].second, t[r].second);
    while(l / 2 != r / 2) {
        if(l % 2 == 0) mx = max(mx, t[l + 1].first), mn = min(mn, t[l + 1].second);
        if(r % 2 == 1) mx = max(mx, t[r - 1].first), mn = min(mn, t[r - 1].second);
        l /= 2; r /= 2;
    }
    return {mx, mn};
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, q;
    cin >> n;
    vector<ll> h(n), a(n), b(n);
    rep(i, 0, n) cin >> h[i] >> a[i] >> b[i];
    cin >> q;

    if(n <= 2000) {
        int st[n][n][maxLog];
        repIn(i, st) repIn(ii, i) repIn(iii, ii) iii = -1;
        rep(i, 0, n - 1) rep(j, i + 1, n) {
            if(a[i] + i > j || b[i] + i < j) continue;
            if(j - a[j] < i || j - b[j] > i) continue;
            st[i][j][0] = st[j][i][0] = abs(h[i] - h[j]);
            DC << i << ' ' << j << ' ' << st[i][j][0] << eol;;
        }
        rep(k, 1, maxLog) rep(i, 0, n) rep(j, 0, n) {
            int i1 = min(n - 1, i + (1 << (k - 1)));
            int j1 = min(n - 1, j + (1 << (k - 1)));
            st[i][j][k] = max(max(st[i][j][k - 1], st[i][j1][k - 1]), max(st[i1][j][k - 1], st[i1][j1][k - 1]));
        }
        int l, r;
        rep(i, 0, q) {
            cin >> l >> r;
            l--; r--;   
            int k = 31 - __builtin_clz(r - l + 1);
            int r1 = r - (1 << k) + 1;
            int ans =max(max(st[l][l][k], st[l][r1][k]), max(st[r1][l][k], st[r1][r1][k]));
            cout << ans << '\n';
        }
    }

    else if(q == 1) {
        int l, r;
        cin >> l >> r;
        if(0 && (l != 1 || r != n)) return 0;
        ll ans = -1;
        vector<pair<int, int>> updates;

        rep(i, 0, n) updates.pb({i - b[i], i + 1}), updates.pb({i - a[i] + 1, -i - 1});
        ranges::sort(updates);
        repIn(i, t) i = {-1, 1e18 + 1};
        auto it = updates.begin();
        rep(i, 0, n) {
            while(it != updates.end() && it -> first <= i) {
                auto upd = it -> second;
                if(upd > 0) {
                    upd--;
                    ts(upd, h[upd]);
                }
                else {
                    upd = - upd - 1;
                    ts(upd, {-1, 1e18 + 1});
                }
                it++;
            }
            auto [mx, mn] = tq(i + a[i], i + b[i]);
            if(mx == -1) continue;
            ans = max(ans, max(abs(mx - h[i]), abs(mn - h[i])));
        }
        updates.clear();

        ranges::reverse(h);
        ranges::reverse(a);
        ranges::reverse(b);

        rep(i, 0, n) updates.pb({i - b[i], i + 1}), updates.pb({i - a[i] + 1, -i - 1});
        ranges::sort(updates);
        repIn(i, t) i = {-1, 1e18 + 1};
        it = updates.begin();
        rep(i, 0, n) {
            while(it != updates.end() && it -> first <= i) {
                auto upd = it -> second;
                if(upd > 0) {
                    upd--;
                    ts(upd, h[upd]);
                }
                else {
                    upd = - upd - 1;
                    ts(upd, {-1, 1e18 + 1});
                }
                it++;
            }
            auto [mx, mn] = tq(i + a[i], i + b[i]);
            if(mx == -1) continue;
            ans = max(ans, max(abs(mx - h[i]), abs(mn - h[i])));
        }
        updates.clear();
        cout << ans << '\n';

    }

}

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