Submission #635265

#	Time	Username	Problem	Language	Result	Execution time	Memory
635265		tutis	Radio Towers (IOI22_towers)	C++17	4 / 100	3393 ms	71760 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;
    pair<int, int> mni;
    pair<int, int> mxi;
    ST() {}
    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);
            mni = min(left->mni, right->mni);
            mxi = max(left->mxi, right->mxi);
        }
        else
        {
            left = right = NULL;
            mn = H[l];
            mni = mxi = {H[l], l};
        }
    }
    int get(int x, int y)
    {
        if (x <= l && r <= y)
            return mn;
        if (r < x || y < l)
            return 2e9;
        return min(left->get(x, y), right->get(x, y));
    }
    pair<int, int> getmx(int x, int y)
    {
        if (x <= l && r <= y)
            return mxi;
        if (r < x || y < l)
            return { -2e9, 0};
        return max(left->getmx(x, y), right->getmx(x, y));
    }
    pair<int, int> getmn(int x, int y)
    {
        if (x <= l && r <= y)
            return mni;
        if (r < x || y < l)
            return { 2e9, 0};
        return min(left->getmn(x, y), right->getmn(x, y));
    }
} 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 = -1;
    int yy = -1;
    if (L != N - 1)
    {
        int lo = L + 1;
        int hi = N - 1;
        while (lo < hi)
        {
            int m = (lo + hi) / 2;
            if (medis.getmx(L + 1, m).first - medis.getmn(L, m - 1).first >= D)
                hi = m;
            else
                lo = m + 1;
        }
        int m = lo;
        pair<int, int>a = medis.getmx(L + 1, m);
        pair<int, int>b = medis.getmn(L, m - 1);
        if (a.first - b.first >= D)
        {
            if (a.second >= b.second)
                xx = a.second;
            else
                xx = nxt[a.second];
        }
    }
    if (R != 0)
    {
        int lo = 0;
        int hi = R - 1;
        while (lo < hi)
        {
            int m = (lo + hi + 1) / 2;
            if (medis.getmx(m, R - 1).first - medis.getmn(m + 1, R).first >= D)
                lo = m;
            else
                hi = m - 1;
        }
        int m = lo;
        pair<int, int>a = medis.getmx(m, R - 1);
        pair<int, int>b = medis.getmn(m + 1, R);
        if (a.first - b.first >= D)
        {
            if (a.second <= b.second)
                yy = a.second;
            else
                yy = prv[a.second];
        }
    }
    if (xx != -1 && yy != -1 && xx <= yy)
        return 2 + get(xx, yy, D);
    return 1;
}

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