Submission #635283

#	Time	Username	Problem	Language	Result	Execution time	Memory
635283		tutis	Radio Towers (IOI22_towers)	C++17	100 / 100	2190 ms	127964 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
vector<int>H;
struct ST
{
    int l, r;
    ST *left, *right;
    int mn;
    ST() {}
    vector<pair<int, int>>V;
    vector<pair<int, int>>W;
    vector<pair<int, int>>V_;
    vector<pair<int, int>>W_;
    ST(int l, int r): l(l), r(r)
    {
        if (l < r)
        {
            left = new ST(l, (l + r) / 2);
            right = new ST((l + r) / 2 + 1, r);
            mn = min(left->mn, right->mn);
        }
        else
        {
            left = right = NULL;
            mn = H[l];
        }
        {
            for (int i = l; i <= r; i++)
            {
                if (W.empty() || H[i] > W.back().first)
                    W.push_back({H[i], i});
            }
            int mm = 1.1e9;
            for (int i = l + 1; i <= r; i++)
            {
                mm = min(mm, H[i - 1]);
                if (V.empty() || H[i] - mm > V.back().first)
                    V.push_back({H[i] - mm, i});
            }
        }
        {
            for (int i = r; i >= l; i--)
            {
                if (W_.empty() || H[i] > W_.back().first)
                    W_.push_back({H[i], i});
            }
            int mm = 1.1e9;
            for (int i = r - 1; i >= l; i--)
            {
                mm = min(mm, H[i + 1]);
                if (V_.empty() || H[i] - mm > V_.back().first)
                    V_.push_back({H[i] - mm, i});
            }
        }
    }
    int get(int x, int y)
    {
        if (x <= l && r <= y)
            return mn;
        if (r < x || y < l)
            return 1.1e9;
        return min(left->get(x, y), right->get(x, y));
    }
    pair<int, int> get1(int L, int D, int mnl = 1.1e9)
    {
        if (L <= l)
        {
            int rr = -1;
            auto it = lower_bound(V.begin(), V.end(), make_pair(D, -1));
            if (it != V.end())
                rr = it->second;
            //W-mn>=D
            //W>=D+mn
            it = lower_bound(W.begin(), W.end(), make_pair(D + mnl, -1));
            if (it != W.end())
            {
                int r1 = it->second;
                if (rr == -1)
                    rr = r1;
                else
                    rr = min(rr, r1);
            }
            return {rr, mn};
        }
        if (r < L)
            return { -1, 1.1e9};
        pair<int, int> i = left->get1(L, D, mnl);
        pair<int, int> j = right->get1(L, D, min(i.second, mnl));
        j.second = min(j.second, i.second);
        if (i.first != -1)
            j.first = i.first;
        return j;
    }
    pair<int, int> get2(int R, int D, int mnl = 1.1e9)
    {
        if (R >= r)
        {
            int rr = -1;
            auto it = lower_bound(V_.begin(), V_.end(), make_pair(D, -1));
            if (it != V_.end())
                rr = it->second;
            //W-mn>=D
            //W>=D+mn
            it = lower_bound(W_.begin(), W_.end(), make_pair(D + mnl, -1));
            if (it != W_.end())
            {
                int r1 = it->second;
                if (rr == -1)
                    rr = r1;
                else
                    rr = max(rr, r1);
            }
            return {rr, mn};
        }
        if (l > R)
            return { -1, 1.1e9};
        pair<int, int> i = right->get2(R, D, mnl);
        pair<int, int> j = left->get2(R, D, min(i.second, mnl));
        j.second = min(j.second, i.second);
        if (i.first != -1)
            j.first = i.first;
        return j;
    }
} medis;
vector<vector<pair<int, int>>>Fl, Fr;
int N;
vector<int>prv;
vector<int>nxt;
void init(int N_, vector<int> H_) {
    N = N_;
    H = H_;
    prv = vector<int>(N, -1);
    nxt = vector<int>(N, N + 1);
    {
        vector<int>A;
        for (int i = 0; i < N; i++)
        {
            while (!A.empty() && H[A.back()] <= H[i])
                A.pop_back();
            if (!A.empty())
                prv[i] = A.back();
            A.push_back(i);
        }
        A.clear();
        for (int i = N - 1; i >= 0; i--)
        {
            while (!A.empty() && H[A.back()] <= H[i])
                A.pop_back();
            if (!A.empty())
                nxt[i] = A.back();
            A.push_back(i);
        }
    }
    vector<int> p(N);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int a, int b) {return H[a] > H[b];});
    set<int>X;
    medis = ST(0, N - 1);
    auto get = [&](int l, int r)
    {
        if (l + 1 >= r)
            return -1;
        int h = medis.get(l + 1, r - 1);
        return max(0, min(H[l] - h, H[r] - h));
    };
    map<int, vector<pair<int, int>>>L;
    map<int, vector<pair<int, int>>>R;
    auto add = [&](int l, int r, int d, int w)
    {
        R[d].push_back({r, w});
        L[d].push_back({l, w});
    };
    for (int i : p)
    {
        int r = -1, l = -1;
        auto it = X.lower_bound(i);
        if (it != X.end())
        {
            r = *it;
        }
        if (it != X.begin())
        {
            it--;
            l = *it;
        }
        X.insert(i);
        if (l == -1 || r == -1)
        {
            if (r != -1 && i + 1 < r)
                add(i, r, get(i, r), 1);
            if (l != -1 && l + 1 < i)
                add(l, i, get(l, i), 1);
        }
        else
        {
            int d = get(l, r);
            int d1 = get(i, r);
            int d2 = get(l, i);
            if (d1 >= 0 || d2 >= 0)
            {
                add(i, r, d1, 1);
                add(l, i, d2, 1);
                assert(max(d1, d2) <= d);
                add(l, r, max(d1, d2), -1);
            }
        }
    }
    Fl = vector<vector<pair<int, int>>>(N);
    Fr = vector<vector<pair<int, int>>>(N);
    for (const auto &dd : L)
    {
        int d = dd.first;
        for (pair<int, int>lw : dd.second)
            for (int i = lw.first; i < N; i |= i + 1)
            {
                if (!Fl[i].empty() && Fl[i].back().first == d)
                    Fl[i].back().second += lw.second;
                else
                    Fl[i].push_back({d, lw.second});
            }
    }
    for (const auto &dd : R)
    {
        int d = dd.first;
        for (pair<int, int>rw : dd.second)
            for (int i = rw.first; i < N; i |= i + 1)
            {
                if (!Fr[i].empty() && Fr[i].back().first == d)
                    Fr[i].back().second += rw.second;
                else
                    Fr[i].push_back({d, rw.second});
            }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 1; j < (int)Fl[i].size(); j++)
            Fl[i][j].second += Fl[i][j - 1].second;
        for (int j = 1; j < (int)Fr[i].size(); j++)
            Fr[i][j].second += Fr[i][j - 1].second;
    }
}
int get(int l, int r, int d)
{
    int ret = 0;
    int i = r;
    while (i >= 0)
    {
        if (!Fr[i].empty())
        {
            auto it = lower_bound(Fr[i].begin(), Fr[i].end(), make_pair(d, (int) - 1e9));
            ret += Fr[i].back().second;
            if (it != Fr[i].begin())
            {
                it--;
                ret -= it->second;
            }
        }
        i = (i & (i + 1)) - 1;
    }
    i = l - 1;
    while (i >= 0) {
        if (!Fl[i].empty())
        {
            auto it = lower_bound(Fl[i].begin(), Fl[i].end(), make_pair(d, (int) - 1e9));
            ret -= Fl[i].back().second;
            if (it != Fl[i].begin())
            {
                it--;
                ret += it->second;
            }
        }
        i = (i & (i + 1)) - 1;
    }
    return ret;
}
int max_towers(int L, int R, int D) {
    int xx = medis.get1(L, D).first;
    int yy = medis.get2(R, D).first;
    if (xx != -1 && yy != -1 && xx <= yy)
        return 2 + get(xx, yy, D);
    return 1;
}

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19
• Subtask 7: 23 / 23