oj.uz

Submission #578363

# Submission time Handle Problem Language Result Execution time Memory
578363 2022-06-16T12:54:58 Z Johann Two Antennas (JOI19_antennas) C++14
0 / 100
 50 ms 4704 KB 
#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);
    }
    int 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";
    }
}

Compilation message

antennas.cpp: In member function 'int Seg2D::compute(int)':
antennas.cpp:51:5: warning: no return statement in function returning non-void [-Wreturn-type]
   51 |     }
      |     ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 768 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 768 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 4704 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 768 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -