Submission #754566

#	Time	Username	Problem	Language	Result	Execution time	Memory
754566		boris_mihov	Radio Towers (IOI22_towers)	C++17	23 / 100	4048 ms	10028 KiB

towers

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>

typedef long long llong;
const int MAXLOG = 20 + 5;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int n;
struct Sparse
{
    int sparse[MAXLOG][MAXN];
    int lg[MAXN];

    void build(int _vals[])
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            sparse[0][i] = _vals[i];
        }

        for (int log = 1 ; (1 << log) <= n ; ++log)
        {
            for (int i = 1 ; i + (1 << log) - 1 <= n ; ++i)
            {
                sparse[log][i] = std::max(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
            }
        }
    
        for (int i = 1 ; i <= n ; ++i)
        {
            lg[i] = lg[i - 1];
            if ((1 << lg[i] + 1) < i)
            {
                lg[i]++;
            }
        }
    }

    int findMAX(int l, int r)
    {
        int log = lg[r - l + 1];
        return std::max(sparse[log][l], sparse[log][r - (1 << log) + 1]);
    }
};

int a[MAXN];
int b[MAXN];
int c[MAXN];
int d[MAXN];
int h[MAXN];
Sparse sparse;
std::stack <int> st;

void init(int N, std::vector <int> H) 
{
    n = N;
    for (int i = 1 ; i <= n ; ++i)
    {
        h[i] = H[i - 1];
    }

    sparse.build(h);
    st.push(0);

    for (int i = 1 ; i <= n ; ++i)
    {
        while (h[st.top()] > h[i])
        {
            st.pop();
        }

        a[i] = st.top();
        st.push(i);
    }

    while (!st.empty())
    {
        st.pop();
    }

    st.push(n + 1);
    for (int i = n ; i >= 1 ; --i)
    {
        while (h[st.top()] > h[i])
        {
            st.pop();
        }

        c[i] = st.top();
        st.push(i);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (a[i] == i - 1)
        {
            b[i] = 0;
        } else
        {
            b[i] = sparse.findMAX(a[i] + 1, i - 1) - h[i];
        }

        if (c[i] == i + 1)
        {
            d[i] = 0;
        } else
        {
            d[i] = sparse.findMAX(i + 1, c[i] - 1) - h[i];
        }
    }
}

int max_towers(int L, int R, int D) 
{
    L++; R++;
    int ans = 0;
    for (int i = L ; i <= R ; ++i)
    {
        if ((a[i] < L || b[i] >= D) && (c[i] > R || d[i] >= D))
        {
            ans++;
        }
    }

    return ans;
}

Compilation message (stderr)

towers.cpp: In member function 'void Sparse::build(int*)':
towers.cpp:30:93: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   30 |                 sparse[log][i] = std::max(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
      |                                                                                         ~~~~^~~
towers.cpp:37:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   37 |             if ((1 << lg[i] + 1) < i)
      |                       ~~~~~~^~~

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