Submission #1279635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279635		yoshi_33550336	Two Antennas (JOI19_antennas)	C++20	100 / 100	956 ms	19380 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
constexpr int B = 240;
template <class E>
struct csr
{
    std::vector<int> start;
    std::vector<E> elist;
    explicit csr(int n, const std::vector<std::pair<int, E>> &edges) : start(n + 1), elist(edges.size())
    {
        for (auto e : edges)
        {
            start[e.first + 1]++;
        }
        for (int i = 1; i <= n; i++)
        {
            start[i] += start[i - 1];
        }
        auto counter = start;
        for (auto e : edges)
        {
            elist[counter[e.first]++] = e.second;
        }
    }

    int N() const
    {
        return start.size();
    }

    int deg(int i) const
    {
        int r = i + 1 == N() ? elist.size() : start[i + 1];
        return r - start[i];
    }

    int begin(int i) const
    {
        return start[i];
    }

    int end(int i) const
    {
        if (i + 1 == N())
            return elist.size();
        return start[i + 1];
    }

    E &operator[](int i) { return elist[i]; }
};

void GetTable(vector<int> &h, vector<int> &a, vector<int> &b, csr<pair<int, int>> &qs, vector<int> &qres, int n)
{
    vector<pair<int, int>> appearance_edge, disappearance_edge;
    for (int i = 0; i < n; i++)
        if (a[i] + i < n)
            appearance_edge.push_back({a[i] + i, i});
    for (int i = 0; i < n; i++)
        if (b[i] + i + 1 < n)
            disappearance_edge.push_back({b[i] + i + 1, i});
    csr<int> appearance(n, appearance_edge);
    csr<int> disappearance(n, disappearance_edge);
    vector<int> re(n, -1);
    vector<int> fc(n, 2e9);
    vector<int> pmin(n / B + 1, 2e9);
    vector<int> lazy(n / B + 1, -1);
    vector<int> maxb(n / B + 1, -1);
    auto PushLazy = [&](const int i)
    {
        for (int k = i / B * B; k < min(n, (i / B + 1) * B); k++)
            re[k] = max(re[k], lazy[i / B] - fc[k]);
        for (int k = i / B * B; k < min(n, (i / B + 1) * B); k++)
            maxb[i / B] = max(maxb[i / B], re[k]);
        lazy[i / B] = -1;
    };
    auto updateFc = [&](const int i, const int p)
    {
        PushLazy(i);
        fc[i] = p;
        pmin[i / B] = 2e9;
        for (int k = i / B * B; k < min(n, (i / B + 1) * B); k++)
            pmin[i / B] = min(pmin[i / B], fc[k]);
    };
    auto updateX = [&](const int l, const int r, const int p)
    {
        PushLazy(l);
        if (l / B == r / B)
        {
            for (int i = l; i <= r; i++)
                re[i] = max(re[i], p - fc[i]);
            for (int i = l; i <= r; i++)
                maxb[l / B] = max(maxb[l / B], re[i]);
        }
        else
        {
            PushLazy(r);
            for (int i = l / B + 1; i < r / B; i++)
                lazy[i] = max(lazy[i], p);
            for (int i = l / B + 1; i < r / B; i++)
                maxb[i] = max(maxb[i], p - pmin[i]);
            for (int i = l; i < (l / B + 1) * B; i++)
                re[i] = max(re[i], p - fc[i]);
            for (int i = r / B * B; i <= r; i++)
                re[i] = max(re[i], p - fc[i]);
            for (int i = l; i < (l / B + 1) * B; i++)
                maxb[l / B] = max(maxb[l / B], re[i]);
            for (int i = r / B * B; i <= r; i++)
                maxb[r / B] = max(maxb[r / B], re[i]);
        }
    };
    auto getX = [&](const int l, const int r)
    {
        int mx = -1;
        PushLazy(l);
        for (int i = l / B + 1; i < r / B; i++)
            mx = max(mx, maxb[i]);
        if (l / B == r / B)
        {
            for (int i = l; i <= r; i++)
                mx = max(mx, re[i]);
        }
        else
        {
            PushLazy(r);
            for (int i = l; i < (l / B + 1) * B; i++)
                mx = max(mx, re[i]);
            for (int i = r / B * B; i <= r; i++)
                mx = max(mx, re[i]);
        }
        return mx;
    };
    for (int i = 1; i < n; i++)
    {
        for (int j = appearance.begin(i); j < appearance.end(i); j++)
            updateFc(appearance.elist[j], h[appearance.elist[j]]);
        for (int j = disappearance.begin(i); j < disappearance.end(i); j++)
            updateFc(disappearance.elist[j], 2e9);
        if (i >= a[i])
            updateX(max(0, i - b[i]), i - a[i], h[i]);
        for (int k = qs.begin(i); k < qs.end(i); k++)
        {
            auto [j, h] = qs.elist[k];
            qres[h] = max(qres[h], getX(j, i));
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n;
    vector<int> h(n), a(n), b(n);
    for (int i = 0; i < n; i++)
        cin >> h[i] >> a[i] >> b[i];
    vector<pair<int, pair<int, int>>> v1p, v2p;
    cin >> q;
    vector<int> qres(q, -1);
    for (int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;
        l--, r--;
        v1p.push_back({r, {l, i}});
        v2p.push_back({n - 1 - l, {n - 1 - r, i}});
    }
    csr<pair<int, int>> v1(n, v1p), v2(n, v2p);
    GetTable(h, a, b, v1, qres, n);
    reverse(h.begin(), h.end());
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    GetTable(h, a, b, v2, qres, n);
    for (int i = 0; i < q; i++)
        cout << qres[i] << '\n';
}

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