Submission #1149445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149445		anmattroi	Two Antennas (JOI19_antennas)	C++20	22 / 100	403 ms	42896 KiB

antennas

#include <bits/stdc++.h>
#define maxn 200005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int n, q;

inline constexpr void cmin(int &x, const int &y) {if (x > y) x = y;}
inline constexpr void cmax(int &x, const int &y) {if (x < y) x = y;}

struct TT {
    int h, a, b;
    TT() {}
    TT(int _h, int _a, int _b) : h(_h), a(_a), b(_b) {}
} tower[maxn];

int kq[maxn];
int rz[maxn];

struct node {
    int historic_max = -1, val = INT_MIN/2, lz = 0, sum = 0, lzsum = 0;
    node() {}
    node(int _historic_max, int _val, int _lz, int _sum, int _lzsum) : historic_max(_historic_max), val(_val), lz(_lz), sum(_sum), lzsum(_lzsum) {}
} st[4*maxn];

void up(int r) {
    cmax(st[r].historic_max, max(st[r<<1].historic_max, st[r<<1|1].historic_max));
    st[r].val = max(st[r<<1].val, st[r<<1|1].val);
    st[r].sum = st[r<<1].sum + st[r<<1|1].sum;
}
void apply(int r, int d, int e) {
    if (st[r].sum) cmax(st[r].historic_max, st[r].val);

    st[r].val += d;
    st[r].lz += d;
    if (st[r].sum)
        cmax(st[r].historic_max, st[r].val);

    st[r].sum += e;
    st[r].lzsum += e;
}

void down(int r) {
    apply(r<<1, st[r].lz, st[r].lzsum);
    apply(r<<1|1, st[r].lz, st[r].lzsum);
    st[r].lz = st[r].lzsum = 0;
}

void update(int u, int v, int d, int e, int r = 1, int lo = 1, int hi = n) {
    if (u > hi || v < lo) return;
    if (u <= lo && hi <= v) {
        apply(r, d, e);
        return;
    }
    down(r);
    int mid = (lo + hi) >> 1;
    update(u, v, d, e, r<<1, lo, mid);
    update(u, v, d, e, r<<1|1, mid+1, hi);
    up(r);
}

void update_change(int u, int d, int e, int r = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        st[r].val = d;
        st[r].sum += e;
        return;
    }
    down(r);
    int mid = (lo + hi) >> 1;
    if (u <= mid) update_change(u, d, e, r<<1, lo, mid);
    else update_change(u, d, e, r<<1|1, mid+1, hi);
    up(r);
}

int get_max(int u, int v, int r = 1, int lo = 1, int hi = n) {
    if (u > hi || v < lo) return -1;
    if (u <= lo && hi <= v) return st[r].historic_max;
    down(r);
    int mid = (lo + hi) >> 1;
    return max(get_max(u, v, r<<1, lo, mid), get_max(u, v, r<<1|1, mid+1, hi));
}

int get_sum(int u, int v, int r = 1, int lo = 1, int hi = n) {
    if (u > hi || v < lo) return 0;
    if (u <= lo && hi <= v) return st[r].sum;
    down(r);
    int mid = (lo + hi) >> 1;
    return get_sum(u, v, r<<1, lo, mid) + get_sum(u, v, r<<1|1, mid+1, hi);
}

vector<ii> queryL[maxn], queryR[maxn];
vector<ii> nho[maxn];


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

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> tower[i].h >> tower[i].a >> tower[i].b;


    cin >> q;
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        queryL[l].emplace_back(r, i);
        queryR[r].emplace_back(l, i);
    }

    for (int i = 1; i <= q; i++) kq[i] = -1;

    for (int i = 1; i <= 4*n; i++) st[i] = node(-1, INT_MIN/2, 0, 0, 0);

    for (int r = 1; r <= n; r++) {
        for (auto [idx, type] : nho[r])
            if (type == 1) update_change(idx, -tower[idx].h, 1);
            else update_change(idx, INT_MIN/2, -1);


        auto [h, a, b] = tower[r];

        int p1 = max(r-b,1), p2 = r-a;
        if (p1 <= p2) update(p1, p2, h, 0);
        for (auto [l, idx] : queryR[r]) {
            cmax(kq[idx], get_max(l, r));
            rz[idx] += get_sum(l, r);
        }
        if (p1 <= p2) update(p1, p2, -h, 0);

        p1 = min(n+1, r+a); p2 = min(n+1, r+b+1);
        nho[p1].emplace_back(r, 1);
        nho[p2].emplace_back(r, 2);
    }
    for (int i = 0; i <= n+1; i++) nho[i].clear();

    for (int i = 1; i <= 4*n; i++) st[i] = node(-1, INT_MIN/2, 0, 0, 0);

    for (int l = n; l >= 1; l--) {
        for (auto [idx, type] : nho[l])
            if (type == 1) update_change(idx, -tower[idx].h, 1);
            else update_change(idx, INT_MIN/2, -1);

        auto [h, a, b] = tower[l];

        int p1 = l+a, p2 = min(n, l+b);

        if (p1 <= p2) update(p1, p2, h, 0);

        for (auto [r, idx] : queryL[l])
            cmax(kq[idx], get_max(l, r));

        if (p1 <= p2) update(p1, p2, -h, 0);

        p1 = max(0, l-a); p2 = max(0, l-b-1);
        nho[p1].emplace_back(l, 1);
        nho[p2].emplace_back(l, 2);
    }

    for (int i = 1; i <= q; i++) cout << (rz[i] ? kq[i] : -1) << "\n";
}
/*
20
260055884 2 15
737689751 5 5
575359903 1 15
341907415 14 14
162026576 9 19
55126745 10 19
95712405 11 14
416027186 8 13
370819848 11 14
629309664 4 13
822713895 5 15
390716905 13 17
577166133 8 19
195931195 10 17
377030463 14 17
968486685 11 19
963040581 4 10
566835557 1 12
586336111 6 16
385865831 8 9
1
1 20

806460109

 */

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