Submission #1215331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215331		Nelt	Radio Towers (IOI22_towers)	C++20	56 / 100	372 ms	20888 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
const ll N = 1e5 + 5, inf = 2e18, lg = 17;
ll a[N], n, lef[N], rig[N], up[lg][N];
ll suf[N];
ll mn[N], mn1[N];
bool flg = 0;
void init(int N, vector<int> H)
{
    n = N;
    for (ll i = 1; i <= n; i++)
        a[i] = H[i - 1];
}
void precomp(ll d)
{
    vector<pair<ll, ll>> st;
    for (ll i = 1; i <= n; i++)
    {
        while (!st.empty() and a[i] > st.back().first)
            st.pop_back();
        auto pos = lower_bound(st.begin(), st.end(), make_pair(a[i] + d - 1, inf), greater());
        if (pos == st.begin())
            lef[i] = 0;
        else
            lef[i] = (pos - 1)->second;
        st.push_back(make_pair(a[i], i));
    }
    while (!st.empty())
        st.pop_back();
    for (ll i = n; i >= 1; i--)
    {
        while (!st.empty() and a[i] > st.back().first)
            st.pop_back();
        auto pos = lower_bound(st.begin(), st.end(), make_pair(a[i] + d - 1, inf), greater());
        if (pos == st.begin())
            rig[i] = n + 1;
        else
            rig[i] = (pos - 1)->second;
        st.push_back(make_pair(a[i], i));
    }
    for (ll i = 1; i <= n; i++)
        mn[i] = suf[i] = mn1[i] = n + 2;
    for (ll i = 1; i <= n; i++)
        mn[lef[i]] = min(mn[lef[i]], rig[i]), mn1[lef[i]] = min(mn1[lef[i]], i), suf[i] = rig[i];
    for (ll i = 0; i < lg; i++) up[i][n + 1] = up[i][n + 2] = n + 2;
    for (ll i = n - 1; i >= 1; i--)
        suf[i] = min(suf[i], suf[i + 1]), mn[i] = min(mn[i + 1], mn[i]), mn1[i] = min(mn1[i + 1], mn1[i]);
    for (ll i = n; i >= 1; i--) 
    {
        up[0][i] = mn[i];
        for (ll j = 1; j < lg; j++) up[j][i] = up[j - 1][up[j - 1][i]];
    }
}
int max_towers(int l, int r, int d)
{
    l++, r++;
    if (!flg)
        precomp(d), flg = 1;
    if (suf[l] > r) return 1;
    l = suf[l];
    ll ans = 1;
    for (ll bit = lg - 1; bit >= 0; bit--) if (up[bit][l] <= r) ans += 1 << bit, l = up[bit][l];
    if (mn1[l] <= r) ans++;
    return ans;
}

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