Submission #578364

#	Time	Username	Problem	Language	Result	Execution time	Memory
578364		Johann	Two Antennas (JOI19_antennas)	C++14	2 / 100	3041 ms	35116 KiB

antennas

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

#define pii pair<int,int>
#define tiii tuple<int,int,int>
#define vi vector<int>
#define vpii vector<pii>
#define vtiii vector<tiii>
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

const int MAXN = 200005;
int A[MAXN], B[MAXN], H[MAXN];

struct Seg2D {
    vi arr;
    int size;
    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        arr.assign(size * size * 2, -1);

        fill(n, 1, 0, 0, size, size);
    }
    void fill(int n, int x, int lox, int loy, int rux, int ruy) {
        if (rux - lox == 1) {
            int i = lox;
            int j = loy;
            if (i >= n || j >= n) return;
            if (!(j - B[j] <= i && i <= j - A[j])) return;
            if (!(i + A[i] <= j && j <= i + B[i])) return;
            arr[x] = abs(H[i] - H[j]);
            return ;
        }
        int mx = (lox + rux) / 2;
        int my = (loy + ruy) / 2;
        fill(n, 4 * x, lox, loy, mx, my);
        fill(n, 4*x+1, mx, loy, rux, my);
        fill(n, 4*x+2, lox, my, mx, ruy);
        fill(n, 4*x+3, mx, my, rux, ruy);
        compute(x);
    }
    void compute(int x) {
        arr[x] = -1;
        if (4 * x + 3 < sz(arr)) {
            arr[x] = max(
                    max(arr[4*x], arr[4*x+1]),
                    max(arr[4*x+2], arr[4*x+3])
                    );
        }
    }
    int query(int l, int r, int x, int lox, int loy, int rux, int ruy) {
        if (rux <= l || r <= lox || ruy <= l || r <= loy) return -1;
        if (l <= lox && rux <= r && l <= loy && ruy <= r) return arr[x];
        int mx = (lox + rux) / 2;
        int my = (loy + ruy) / 2;
        int a = query(l, r, 4 * x, lox, loy, mx, my);
        int b = query(l, r, 4*x+1, mx, loy, rux, my);
        int c = query(l, r, 4*x+2, lox, my, mx, ruy);
        int d = query(l, r, 4*x+3, mx, my, rux, ruy);
        return max( max(a, b), max(c, d) );
    }
    int query(int l, int r) {
        return query(l, r, 1, 0, 0, size, size);
    }
};

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

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) { cin >> H[i] >> A[i] >> B[i]; }

    Seg2D seg;
    seg.init(n);

    int q;
    cin >> q;
    for (int i = 0,l,r; i < q; ++i) {
        cin >> l >> r; --l;
        cout << seg.query(l,r) << "\n";
    }
}

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