Submission #1170140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170140		patgra	Two Antennas (JOI19_antennas)	C++20	13 / 100	422 ms	189964 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 = 0;
#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;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, q;
    cin >> n;
    vector<int> h(n), a(n), b(n);
    rep(i, 0, n) cin >> h[i] >> a[i] >> b[i];
    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;
        cin >> q;
        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';
        }
    }
}

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