Submission #789473

#	Time	Username	Problem	Language	Result	Execution time	Memory
789473		someone	Two Antennas (JOI19_antennas)	C++14	100 / 100	496 ms	63140 KiB

antennas

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

const int M = 1 << 18, N = 2 * M, INF = 1e12 + 42;

struct Node {
    int maxi = -1, maxVal = -INF, minVal = INF, maxTag = -INF, minTag = INF;
};

Node node[N];
vector<int> req[M], upd[N];
int n, q, h[M], a[M], b[M], debReq[M], ans[M];

inline void applyOp(int i, int minTag, int maxTag) {
    node[i].minTag = min(node[i].minTag, minTag);
    node[i].maxTag = max(node[i].maxTag, maxTag);
    node[i].maxi = max(node[i].maxi, node[i].maxVal - minTag);
    node[i].maxi = max(node[i].maxi, maxTag - node[i].minVal);
}

void propage(int i) {
    applyOp(i*2, node[i].minTag, node[i].maxTag);
    applyOp(i*2+1, node[i].minTag, node[i].maxTag);
    node[i].minTag = INF, node[i].maxTag = -INF;
}

void update(int i, int deb, int fin, int l, int r, int newVal) {
    if(fin <= l || r <= deb)
        return;
    if(l <= deb && fin <= r) {
        applyOp(i, newVal, newVal);
        return;
    }
    propage(i);
    int mid = ((deb +  fin) >> 1);
    update(i*2, deb, mid, l, r, newVal);
    update(i*2+1, mid, fin, l, r, newVal);
    node[i].maxi = max(node[i*2].maxi, node[i*2+1].maxi);
}

void setVal(int i, int deb, int fin, int pos, int minVal, int maxVal) {
    if(fin <= pos || pos < deb)
        return;
    if(fin - deb == 1) {
        node[i].minVal = minVal;
        node[i].maxVal = maxVal;
        return;
    }
    propage(i);
    int mid = ((deb +  fin) >> 1);
    setVal(i*2, deb, mid, pos, minVal, maxVal);
    setVal(i*2+1, mid, fin, pos, minVal, maxVal);
    node[i].minVal = min(node[i*2].minVal, node[i*2+1].minVal);
    node[i].maxVal = max(node[i*2].maxVal, node[i*2+1].maxVal);
}

int getMax(int i, int deb, int fin, int l, int r) {
    if(fin <= l || r <= deb)
        return -1;
    if(l <= deb && fin <= r)
        return node[i].maxi;
    propage(i);
    int mid = ((deb +  fin) >> 1),
        val = max(getMax(i*2, deb, mid, l, r),
                  getMax(i*2+1, mid, fin, l, r));
    return val;
}

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


    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> h[i] >> a[i] >> b[i];
    cin >> q;
    for(int i = 0; i < q; i++) {
        int fin; cin >> debReq[i] >> fin;
        debReq[i]--, fin--;
        req[fin].push_back(i);
    }
    for(int i = 0; i < n; i++) {
        for(int j : upd[i]) {
            if(j >= 0) {
                setVal(1, 0, M, j, h[j], h[j]);
            } else {
                setVal(1, 0, M, -j-1, INF, -INF);
            }
        }
        update(1, 0, M, i - b[i], i - a[i] + 1, h[i]);
        for(int j : req[i])
            ans[j] = getMax(1, 0, M, debReq[j], i);

        upd[i + a[i]].push_back(i);
        upd[i + b[i] + 1].push_back(-i-1);
    }
    for(int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

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