oj.uz

Submission #578348

# Submission time Handle Problem Language Result Execution time Memory
578348 2022-06-16T12:08:55 Z Johann Two Antennas (JOI19_antennas) C++14
22 / 100
 258 ms 20552 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()

struct item {
    int mini = INT_MAX;
    int maxi = INT_MIN;
    int res = -1;
    int op = -1;
    bool active = false;
};

struct SegTree {
    vector<item> arr;
    int size;
    void cmp(item & a, item & b, item & res) {
        res.mini = min(
                (a.active) ? a.mini : INT_MAX, (b.active) ? b.mini : INT_MAX );
        res.maxi = max(
                (a.active) ? a.maxi : INT_MIN, (b.active) ? b.maxi : INT_MIN );
        res.res = max(res.res, max(a.res, b.res));
        res.active = a.active | b.active;
    }
    void apply(int x) {
        if (arr[x].op == -1) return;
        int nres =  INT_MIN;
        if (arr[x].active) nres = max(abs(arr[x].mini - arr[x].op), abs(arr[x].maxi - arr[x].op) );
        arr[x].res = max(arr[x].res, nres);
        if (2 * x < sz(arr) && nres > arr[2 * x].res) { apply(2 * x); arr[2 * x].op = arr[x].op; }
        if (2*x+1 < sz(arr) && nres > arr[2*x+1].res) { apply(2*x+1); arr[2*x+1].op = arr[x].op; }
        arr[x].op = -1;
    }
    void init(vi & H) {
        size = 1;
        while (size < sz(H)) size *= 2;
        arr.assign(2 * size, item());
        for (int i = 0; i < sz(H); ++i) {
            arr[size + i].mini = H[i];
            arr[size + i].maxi = H[i];
        }
        for (int i = size-1; i > 0; --i) {
            cmp(arr[2 * i], arr[2 * i + 1], arr[i]);
        }
    }
    void setState(int i, bool state, int x, int lx, int rx ) {
        apply(x);
        if (rx - lx == 1) { arr[x].active = state; return; }
        int m = (lx + rx) / 2;
        if (i < m) setState(i, state, 2 * x, lx, m);
        else setState(i, state, 2 * x + 1, m, rx);
        apply(2*x), apply(2*x+1);
        cmp(arr[2*x], arr[2*x+1], arr[x]);
    }
    void setState(int i, bool state) {
        setState(i, state, 1, 0, size);
    }
    void update(int l, int r, int h, int x, int lx, int rx ) {
        apply(x);
        if (rx <= l || r <= lx) return;
        if (l <= lx && rx <= r) { // in
            arr[x].op = h;
            return;
        }
        int m = (lx + rx) / 2;
        update(l, r, h, 2 * x, lx, m);
        update(l, r, h, 2 * x + 1, m, rx);
        apply(2*x); apply(2*x+1);
        cmp(arr[2*x], arr[2*x+1], arr[x]);
    }
    void update(int l, int r, int h) {
        update(l, r, h, 1, 0, size);
    }
    int query(int l, int r, int x, int lx, int rx ) {
        apply(x);
        if (rx <= l || r <= lx) return -1;
        if (l <= lx && rx <= r) return arr[x].res;
        int m = (lx + rx) / 2;
        int a = query(l, r, 2 * x, lx, m);
        int b = query(l, r, 2 * x + 1, m, rx);
        return max(a,b);
    }
    int query(int l, int r) {
        return query(l, r, 1, 0, size);
    }
};

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

    int n;
    cin >> n;
    vi H(n), A(n), B(n);
    for (int i = 0; i < n; ++i) { cin >> H[i] >> A[i] >> B[i]; }
    int q;
    cin >> q;
    vtiii Q(q);
    for (int i = 0,l,r; i < q; ++i) {
        cin >> l >> r; --l; --r;
        Q[i] = { l, r, i };
    }
    vi ans(q, -1);

    priority_queue<pii, vpii, greater<pii>> activate;
    priority_queue<pii, vpii, greater<pii>> deactivate;

    SegTree seg;
    seg.init(H);
    sort(all(Q), [&](tiii & a, tiii & b){
        return get<1>(a) > get<1>(b);
    }); // Niedrige Endpunkte nach hinten, dann kann man den Vektor als queue verwenden

    for (int i = 0; i < n; ++i) {
        activate.push({i + A[i], i});
        deactivate.push({i + B[i], i});
        while (!activate.empty() && activate.top().first == i) {
            seg.setState(activate.top().second, true);
            activate.pop();
        }

        int l = i - B[i];
        int r = i - A[i] + 1;
        seg.update(l, r, H[i]);

        while (!Q.empty() && get<1>(Q.back()) == i) {
            int idx;
            tie(l,r,idx) = Q.back(); Q.pop_back();
            ans[idx] = seg.query(l,r);
        }

        while(!deactivate.empty() && deactivate.top().first == i) {
            seg.setState(deactivate.top().second, false);
            deactivate.pop();
        }
    }

    for (int x : ans) cout << x << "\n";

}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 15592 KB Output is correct
2 Correct 257 ms 20412 KB Output is correct
3 Correct 176 ms 17208 KB Output is correct
4 Correct 258 ms 20456 KB Output is correct
5 Correct 106 ms 10100 KB Output is correct
6 Correct 252 ms 20436 KB Output is correct
7 Correct 234 ms 18448 KB Output is correct
8 Correct 244 ms 20400 KB Output is correct
9 Correct 32 ms 3156 KB Output is correct
10 Correct 242 ms 20428 KB Output is correct
11 Correct 150 ms 11248 KB Output is correct
12 Correct 242 ms 20552 KB Output is correct
13 Correct 192 ms 20304 KB Output is correct
14 Correct 194 ms 20528 KB Output is correct
15 Correct 182 ms 19276 KB Output is correct
16 Correct 167 ms 19316 KB Output is correct
17 Correct 191 ms 20408 KB Output is correct
18 Correct 179 ms 19256 KB Output is correct
19 Correct 183 ms 20540 KB Output is correct
20 Correct 183 ms 20284 KB Output is correct
21 Correct 186 ms 20280 KB Output is correct
22 Correct 181 ms 20292 KB Output is correct
23 Correct 185 ms 19268 KB Output is correct
24 Correct 173 ms 19384 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -