Submission #1295863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295863		peanut	Two Antennas (JOI19_antennas)	C++20	13 / 100	336 ms	589824 KiB

antennas

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 5;

int n, q;
int h[maxn], a[maxn], b[maxn];

namespace subtask12 {
    bool check() {return n <= 2000;}
    void solve() {
        vector<vector<int>> L(n+1, vector<int>(n+1, -1));
        for (int i = 1; i <= n; ++i) {
            if (i+a[i] > n) continue;
            for (int j = i+a[i]; j <= min(n, i+b[i]); ++j) {
                L[i][j] = L[i][j-1];
                if (j-b[j] <= i && i <= j-a[j]) L[i][j] = max(L[i][j], abs(h[i] - h[j]));
            }
            for (int j = i+b[i]+1; j <= n; ++j) L[i][j] = L[i][j-1];
        }
        vector<vector<int>> ans(n+1, vector<int>(n+1, -1));
        for (int i = 1; i <= n; ++i) {
            for (int j = i-1; j >= 1; --j) ans[j][i] = max(ans[j+1][i], L[j][i]);
        }
        cin >> q;
        while (q--) {
            int l, r; cin >> l >> r;
            cout << ans[l][r] << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> h[i] >> a[i] >> b[i];
    }
    subtask12::solve();
    return 0;
}

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