oj.uz

Submission #754594

# Submission time Handle Problem Language Result Execution time Memory
754594 2023-06-08T06:44:46 Z boris_mihov Radio Towers (IOI22_towers) C++17
4 / 100
 933 ms 16764 KB 
#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;
std::vector <int> v;
int isClimb = -1;

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);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if ((i == 1 || h[i - 1] < h[i]) && (i == n || h[i] > h[i + 1]))
        {
            isClimb = i;
            break;
        }
    }

    for (int i = 1 ; i < isClimb ; ++i)
    {
        if (h[i] > h[i + 1])
        {
            isClimb = -1;
            break;
        }
    }

    if (isClimb != -1)
    {
        for (int i = isClimb ; i < n ; ++i)
        {
            if (h[i] < h[i + 1])
            {
                isClimb = -1;
                break;
            }
        }
    }

    assert(isClimb != -1);

    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];
        }
    }

    v.push_back(d[1]);
    v.push_back(b[n]);
    for (int i = 2 ; i < n ; ++i)
    {
        v.push_back(std::min(b[i], d[i]));
    }

    std::sort(v.begin(), v.end());
}

bool entered;
int max_towers(int L, int R, int D) 
{
    L++; R++;
    if (isClimb != -1)
    {
        if (isClimb < L || R < isClimb)
        {
            return 1;
        }

        if (h[L] + D <= h[isClimb] && h[R] + D <= h[isClimb])
        {
            return 2;
        }

        return 1;
    }

    if (L == R)
    {
        return 1;
    }

    if (L == 1 && R == n)
    {
        int l = -1, r = n, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (v[mid] < D) l = mid;
            else r = mid;
        }

        return n - 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

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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 6224 KB Output is correct
2 Correct 634 ms 10404 KB Output is correct
3 Correct 933 ms 10492 KB Output is correct
4 Correct 839 ms 10436 KB Output is correct
5 Correct 724 ms 10572 KB Output is correct
6 Correct 804 ms 10440 KB Output is correct
7 Correct 743 ms 10660 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 16764 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 4048 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 6224 KB Output is correct
2 Correct 634 ms 10404 KB Output is correct
3 Correct 933 ms 10492 KB Output is correct
4 Correct 839 ms 10436 KB Output is correct
5 Correct 724 ms 10572 KB Output is correct
6 Correct 804 ms 10440 KB Output is correct
7 Correct 743 ms 10660 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Runtime error 1 ms 592 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -