Submission #1149479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149479		anmattroi	Two Antennas (JOI19_antennas)	C++20	100 / 100	791 ms	50476 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];

constexpr int MINF = INT_MIN/2;

struct node {
    int valA, valB, lz, hlz;
    node() {}
    node(int _valA, int _valB, int _lz, int _hlz) : valA(_valA), valB(_valB), lz(_lz), hlz(_hlz) {}
} st[4*maxn];


void apple(int r, const node &other) {
    cmax(st[r].valB, st[r].valA + other.hlz);
    cmax(st[r].hlz, st[r].lz + other.hlz);
    st[r].lz += other.lz;
    st[r].valA += other.lz;
}

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

void update(int u, int v, int d, int r = 1, int lo = 1, int hi = n) {
    if (u > hi || v < lo) return;
    if (u <= lo && hi <= v) {
        apple(r, node(0, 0, d, max(d, 0)));
        return;
    }
    down(r);
    int mid = (lo + hi) >> 1;
    update(u, v, d, r<<1, lo, mid);
    update(u, v, d, r<<1|1, mid+1, hi);
    st[r].valA = max(st[r<<1].valA, st[r<<1|1].valA);
    st[r].valB = max(st[r<<1].valB, st[r<<1|1].valB);
}

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].valB;
    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));
}

void rs() {
    for (int i = 1; i <= 4*n; i++) st[i] = node(MINF, MINF, 0, 0);
}

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;

    rs();

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


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

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

        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();

    rs();

    for (int l = n; l >= 1; l--) {
        for (auto [idx, type] : nho[l])
            if (type == 1) update(idx, idx, -(MINF)-tower[idx].h);
            else update(idx, idx, tower[idx].h + MINF);

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

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

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

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

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

        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 << kq[i] << "\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: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65