Submission #1149308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149308		anmattroi	Two Antennas (JOI19_antennas)	C++17	2 / 100	3096 ms	53044 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;
constexpr int B = 450;
inline constexpr int csk(const int &u) {return (u-1)/B+1;}
inline constexpr int csd(const int &u) {return (u-1)*B+1;}
inline constexpr int csc(const int &u) {return min(n,u*B);}

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 node {
    int h, a, b;
    node() {}
    node(int _h, int _a, int _b) : h(_h), a(_a), b(_b) {}
} tower[maxn];

vector<ii> nho[maxn];

int stmin[2*maxn], stmax[2*maxn];

multiset<int> rem[maxn];

void upd(int u) {
    int v = u;
    u = v+n;
    for (stmin[u] = (rem[v].empty() ? INT_MAX/2 : *rem[v].begin()); u >>= 1;) stmin[u] = min(stmin[u<<1], stmin[u<<1|1]);
    u = v+n;
    for (stmax[u] = (rem[v].empty() ? INT_MIN/2 : *rem[v].rbegin());u >>= 1;) stmax[u] = max(stmax[u<<1], stmax[u<<1|1]);
}

int getmin(int u, int v) {
    int kq = INT_MAX/2;
    for (u += n, v += n + 1; u < v; u >>= 1, v >>= 1) {
        if (u&1) kq = min(kq, stmin[u++]);
        if (v&1) kq = min(kq, stmin[--v]);
    }
    return kq;
}

int getmax(int u, int v) {
    int kq = INT_MIN/2;
    for (u += n, v += n + 1; u < v; u >>= 1, v >>= 1) {
        if (u&1) kq = max(kq, stmax[u++]);
        if (v&1) kq = max(kq, stmax[--v]);
    }
    return kq;
}

int f[451][maxn], g[451][maxn];

int solve_range(int u, int v) {
    int kq = -1;
    for (int i = u; i <= v+1; i++) {
        for (auto [idx, type] : nho[i]) {
            if (type == 1) rem[idx].insert(tower[idx].h);
            else rem[idx].erase(rem[idx].find(tower[idx].h));
            upd(idx);
        }
        nho[i].clear();
        if (i == v+1) break;
        auto [h, a, b] = tower[i];
        nho[min(v+1,i+a)].emplace_back(i, 1);
        nho[min(v+1,i+b+1)].emplace_back(i, 2);
        kq = max({kq, h-getmin(max(u, i-b), i-a), getmax(max(u,i-b),i-a)-h});
    }
    return kq;
}

ii Intersect(const ii &x, const ii &y) {
    ii T = {max(x.fi, y.fi), min(x.se, y.se)};
    if (T.fi > T.se) return {-1, -1};
    return T;
}
void solve(int l, int r) {
    int u = csk(l), v = csk(r);
    if (v-u <= 1) {
        cout << solve_range(l, r) << "\n";
        return;
    }

    int kq = max(f[u][r], g[v][l]);

    int START = l, STOP = csc(u);

    for (int i = START; i <= STOP+1; i++) {
        for (auto [idx, type] : nho[i]) {
            if (type == 1) rem[idx].insert(tower[idx].h);
            else rem[idx].erase(rem[idx].find(tower[idx].h));
            upd(idx);
        }
        nho[i].clear();
        if (i == STOP+1) break;
        auto [h, a, b] = tower[i];
        ii range = {i+a, i+b+1};
        ii O1 = Intersect(range, ii{START, STOP+1});
        ii O2 = Intersect(range, ii{csd(v), r+1});

        if (O1.fi != -1) {
            nho[O1.fi].emplace_back(i, 1);
            nho[O1.se].emplace_back(i, 2);
        }
        if (O2.fi != -1) {
            nho[O2.fi].emplace_back(i, 1);
            nho[O2.se].emplace_back(i, 2);
        }
        nho[min(STOP+1,i+a)].emplace_back(i, 1);
        nho[min(STOP+1,i+b+1)].emplace_back(i, 2);
        kq = max({kq, h-getmin(max(START, i-b), i-a), getmax(max(START,i-b),i-a)-h});
    }

    START = csd(v); STOP = r;
    for (int i = START; i <= STOP+1; i++) {
        for (auto [idx, type] : nho[i]) {
            if (type == 1) rem[idx].insert(tower[idx].h);
            else rem[idx].erase(rem[idx].find(tower[idx].h));
            upd(idx);
        }
        nho[i].clear();
        if (i == STOP+1) break;
        auto [h, a, b] = tower[i];
        nho[min(STOP+1,i+a)].emplace_back(i, 1);
        nho[min(STOP+1,i+b+1)].emplace_back(i, 2);
        kq = max({kq, h-getmin(max(START, i-b), i-a), getmax(max(START,i-b),i-a)-h});
    }

    cout << kq << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= 2*n+1; i++) {
        stmin[i] = INT_MAX/2;
        stmax[i] = INT_MIN/2;
    }
    for (int i = 1; i <= n; i++) cin >> tower[i].h >> tower[i].a >> tower[i].b;

    for (int o = 1; o <= csk(n); o++) {
        int l = csd(o);
        nho[min(n+1, l+tower[l].a)].emplace_back(l, 1);
        nho[min(n+1, l+tower[l].b+1)].emplace_back(l, 2);

        f[o][l] = -1;
        for (int r = l+1; r <= n+1; r++) {
            f[o][r] = -1;
            for (auto [idx, type] : nho[r]) {
                if (type == 1) rem[idx].insert(tower[idx].h);
                else rem[idx].erase(rem[idx].find(tower[idx].h));
                upd(idx);
            }
            nho[r].clear();
            if (r == n+1) break;
            auto [h, a, b] = tower[r];
            nho[min(n+1, r+a)].emplace_back(r, 1);
            nho[min(n+1, r+b+1)].emplace_back(r, 2);
            f[o][r] = f[o][r-1];
            f[o][r] = max({f[o][r], h-getmin(max(1, r-b), r-a), getmax(max(1,r-b),r-a)-h});
        }
    }

    for (int o = 1; o <= csk(n); o++) {
        int l = csc(o);
        nho[max(0, l-tower[l].a)].emplace_back(l, 1);
        nho[max(0, l-tower[l].b-1)].emplace_back(l, 2);

        g[o][l] = -1;
        for (int r = l-1; r >= 0; r--) {
            g[o][r] = -1;
            for (auto [idx, type] : nho[r]) {
                if (type == 1) rem[idx].insert(tower[idx].h);
                else rem[idx].erase(rem[idx].find(tower[idx].h));
                upd(idx);
            }
            nho[r].clear();
            if (r == 0) break;
            auto [h, a, b] = tower[r];
            nho[max(0, r-a)].emplace_back(r, 1);
            nho[max(0, r-b-1)].emplace_back(r, 2);
            g[o][r] = g[o][r+1];
            g[o][r] = max({g[o][r], h-getmin(r+a, min(r+b, n)), getmax(r+a, min(r+b, n))-h});
        }
    }

    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        solve(l, r);
    }
}

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