oj.uz

Submission #754640

# Submission time Handle Problem Language Result Execution time Memory
754640 2023-06-08T07:37:47 Z boris_mihov Radio Towers (IOI22_towers) C++17
35 / 100
 1507 ms 52708 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 MST
{
    std::vector <int> tree[4*MAXN];
    void build(int l, int r, int node, int vals[])
    {
        if (l == r)
        {
            tree[node].push_back(vals[l]);
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node, vals);
        build(mid + 1, r, 2*node + 1, vals);
        tree[node].reserve(r - l + 1);

        int lPtr = 0, rPtr = 0;
        for (int i = l ; i <= r ; ++i)
        {
            if (lPtr == tree[2*node].size())
            {
                tree[node].push_back(tree[2*node + 1][rPtr++]);
                continue;
            }

            if (rPtr == tree[2*node + 1].size())
            {
                tree[node].push_back(tree[2*node][lPtr++]);
                continue;
            }

            if (tree[2*node][lPtr] < tree[2*node + 1][rPtr])
            {
                tree[node].push_back(tree[2*node][lPtr++]);
            } else
            {
                tree[node].push_back(tree[2*node + 1][rPtr++]);
            }
        }
    }

    int binary(int node, int val)
    {
        int l = -1, r = tree[node].size(), mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (tree[node][mid] < val) l = mid;
            else r = mid;
        }

        return r;
    }

    int query(int l, int r, int node, int queryL, int queryR, int queryVal)
    {
        if (queryL <= l && r <= queryR)
        {
            return binary(node, queryVal);
        }

        int res = 0;
        int mid = (l + r) / 2;
        if (queryL <= mid) res += query(l, mid, 2*node, queryL, queryR, queryVal);
        if (mid + 1 <= queryR) res += query(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
        return res;
    }

    void build(int vals[])
    {
        build(1, n, 1, vals);
    }

    int query(int l, int r, int val)
    {
        return query(1, n, 1, l, r, val);
    }
};

MST left, right;
struct Sparse
{
    int sparse[MAXLOG][MAXN];
    int vals[MAXN];
    int lg[MAXN];

    int cmp(int x, int y)
    {
        if (vals[x] > vals[y]) return x;
        return y;
    }

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

        for (int log = 1 ; (1 << log) <= n ; ++log)
        {
            for (int i = 1 ; i + (1 << log) - 1 <= n ; ++i)
            {
                sparse[log][i] = cmp(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 vals[cmp(sparse[log][l], sparse[log][r - (1 << log) + 1])];
    }

    int findIDX(int l, int r)
    {
        int log = lg[r - l + 1];
        return cmp(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;
            }
        }
    }

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

    for (int i = 1 ; i <= n ; ++i)
    {
        int curr = INF; 
        if (a[i] > 0) curr = std::min(curr, b[i]);
        if (c[i] < n + 1) curr = std::min(curr, d[i]);
        v.push_back(curr);
    }

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

bool entered;
int vals[MAXN];
int prefix[MAXN];
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;
    }

    if (!entered)
    {
        entered = true;
        for (int i = 1 ; i <= n ; ++i)
        {
            if ((a[i] > 0 && b[i] < D) && (c[i] == n + 1 || d[i] >= D))
            {
                vals[i] = a[i];
            } else
            {
                vals[i] = INF;
            }
        }

        left.build(vals);
        for (int i = 1 ; i <= n ; ++i)
        {
            if ((c[i] <= n && d[i] < D) && (a[i] == 0 || b[i] >= D))
            {
                vals[i] = c[i];
            } else
            {
                vals[i] = 0;
            }
        }

        right.build(vals);
        for (int i = 1 ; i <= n ; ++i)
        {
            prefix[i] = prefix[i - 1];
            if ((a[i] == 0 || b[i] >= D) && (c[i] == n + 1 || d[i] >= D))
            {
                prefix[i]++;
            }
        }
    }

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

    int add = 0;
    int idx = sparse.findIDX(L, R);
    if (a[idx] < L && c[idx] > R) add++;
    if (a[idx] == 0 && a[idx] == n + 1) add++;
    return prefix[R] - prefix[L - 1] + left.query(L, R, L) + (R - L + 1 - right.query(L, R, R + 1)) + add;
}

Compilation message

towers.cpp: In member function 'void MST::build(int, int, int, int*)':
towers.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             if (lPtr == tree[2*node].size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
towers.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             if (rPtr == tree[2*node + 1].size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp: In member function 'void Sparse::build(int*)':
towers.cpp:118:88: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  118 |                 sparse[log][i] = cmp(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
      |                                                                                    ~~~~^~~
towers.cpp:125:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  125 |             if ((1 << lg[i] + 1) < i)
      |                       ~~~~~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 25236 KB Output is correct
2 Correct 1025 ms 29624 KB Output is correct
3 Correct 759 ms 29572 KB Output is correct
4 Correct 903 ms 29724 KB Output is correct
5 Correct 751 ms 29820 KB Output is correct
6 Correct 827 ms 29712 KB Output is correct
7 Correct 841 ms 29832 KB Output is correct
8 Correct 10 ms 19084 KB Output is correct
9 Correct 12 ms 19280 KB Output is correct
10 Correct 10 ms 19280 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19152 KB Output is correct
2 Correct 15 ms 19664 KB Output is correct
3 Correct 12 ms 19664 KB Output is correct
4 Correct 11 ms 19628 KB Output is correct
5 Correct 13 ms 19664 KB Output is correct
6 Correct 11 ms 19664 KB Output is correct
7 Correct 11 ms 19680 KB Output is correct
8 Correct 11 ms 19280 KB Output is correct
9 Correct 11 ms 19264 KB Output is correct
10 Incorrect 11 ms 19664 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
11 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19152 KB Output is correct
2 Correct 15 ms 19664 KB Output is correct
3 Correct 12 ms 19664 KB Output is correct
4 Correct 11 ms 19628 KB Output is correct
5 Correct 13 ms 19664 KB Output is correct
6 Correct 11 ms 19664 KB Output is correct
7 Correct 11 ms 19680 KB Output is correct
8 Correct 11 ms 19280 KB Output is correct
9 Correct 11 ms 19264 KB Output is correct
10 Incorrect 11 ms 19664 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
11 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1045 ms 52224 KB Output is correct
2 Correct 1287 ms 52444 KB Output is correct
3 Correct 1507 ms 52476 KB Output is correct
4 Correct 1411 ms 52540 KB Output is correct
5 Correct 1228 ms 52576 KB Output is correct
6 Correct 1313 ms 52416 KB Output is correct
7 Correct 1120 ms 52472 KB Output is correct
8 Correct 707 ms 29696 KB Output is correct
9 Correct 906 ms 29732 KB Output is correct
10 Correct 1361 ms 52464 KB Output is correct
11 Correct 1166 ms 52708 KB Output is correct
12 Correct 940 ms 29640 KB Output is correct
13 Correct 716 ms 29836 KB Output is correct
14 Correct 11 ms 19024 KB Output is correct
15 Correct 12 ms 19280 KB Output is correct
16 Correct 12 ms 19272 KB Output is correct
17 Correct 82 ms 52520 KB Output is correct
18 Correct 83 ms 52412 KB Output is correct
19 Correct 77 ms 52496 KB Output is correct
20 Correct 38 ms 29764 KB Output is correct
21 Correct 74 ms 52488 KB Output is correct
22 Correct 32 ms 29380 KB Output is correct
23 Correct 32 ms 29336 KB Output is correct
24 Correct 31 ms 29336 KB Output is correct
25 Correct 37 ms 29732 KB Output is correct
26 Correct 30 ms 29572 KB Output is correct
27 Correct 11 ms 19664 KB Output is correct
28 Correct 11 ms 19632 KB Output is correct
29 Correct 12 ms 19664 KB Output is correct
30 Correct 10 ms 19280 KB Output is correct
31 Correct 11 ms 19664 KB Output is correct
32 Correct 11 ms 19284 KB Output is correct
33 Correct 13 ms 19280 KB Output is correct
34 Correct 10 ms 19216 KB Output is correct
35 Correct 10 ms 19280 KB Output is correct
36 Correct 11 ms 19280 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 21492 KB Output is correct
2 Correct 758 ms 29340 KB Output is correct
3 Correct 781 ms 29388 KB Output is correct
4 Correct 830 ms 29332 KB Output is correct
5 Correct 892 ms 29324 KB Output is correct
6 Correct 921 ms 29368 KB Output is correct
7 Correct 881 ms 29324 KB Output is correct
8 Correct 899 ms 29684 KB Output is correct
9 Correct 657 ms 29764 KB Output is correct
10 Correct 626 ms 29604 KB Output is correct
11 Correct 761 ms 29640 KB Output is correct
12 Correct 44 ms 29380 KB Output is correct
13 Correct 44 ms 29332 KB Output is correct
14 Correct 35 ms 29316 KB Output is correct
15 Correct 32 ms 29900 KB Output is correct
16 Correct 30 ms 29712 KB Output is correct
17 Correct 33 ms 29204 KB Output is correct
18 Correct 33 ms 29320 KB Output is correct
19 Correct 33 ms 29380 KB Output is correct
20 Correct 32 ms 29380 KB Output is correct
21 Correct 35 ms 29344 KB Output is correct
22 Correct 34 ms 29380 KB Output is correct
23 Correct 49 ms 29340 KB Output is correct
24 Correct 38 ms 29728 KB Output is correct
25 Correct 30 ms 29764 KB Output is correct
26 Correct 29 ms 29568 KB Output is correct
27 Correct 32 ms 29712 KB Output is correct
28 Correct 11 ms 19256 KB Output is correct
29 Correct 13 ms 19276 KB Output is correct
30 Correct 11 ms 19280 KB Output is correct
31 Correct 11 ms 19340 KB Output is correct
32 Correct 11 ms 19280 KB Output is correct
33 Correct 10 ms 19220 KB Output is correct
34 Correct 12 ms 19344 KB Output is correct
35 Correct 10 ms 19280 KB Output is correct
36 Correct 11 ms 19280 KB Output is correct
37 Correct 12 ms 19280 KB Output is correct
38 Correct 11 ms 19280 KB Output is correct
39 Correct 11 ms 19304 KB Output is correct
40 Correct 11 ms 19288 KB Output is correct
41 Correct 10 ms 19276 KB Output is correct
42 Correct 11 ms 19280 KB Output is correct
43 Correct 10 ms 19280 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19152 KB Output is correct
2 Correct 15 ms 19664 KB Output is correct
3 Correct 12 ms 19664 KB Output is correct
4 Correct 11 ms 19628 KB Output is correct
5 Correct 13 ms 19664 KB Output is correct
6 Correct 11 ms 19664 KB Output is correct
7 Correct 11 ms 19680 KB Output is correct
8 Correct 11 ms 19280 KB Output is correct
9 Correct 11 ms 19264 KB Output is correct
10 Incorrect 11 ms 19664 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
11 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 25236 KB Output is correct
2 Correct 1025 ms 29624 KB Output is correct
3 Correct 759 ms 29572 KB Output is correct
4 Correct 903 ms 29724 KB Output is correct
5 Correct 751 ms 29820 KB Output is correct
6 Correct 827 ms 29712 KB Output is correct
7 Correct 841 ms 29832 KB Output is correct
8 Correct 10 ms 19084 KB Output is correct
9 Correct 12 ms 19280 KB Output is correct
10 Correct 10 ms 19280 KB Output is correct
11 Correct 13 ms 19152 KB Output is correct
12 Correct 15 ms 19664 KB Output is correct
13 Correct 12 ms 19664 KB Output is correct
14 Correct 11 ms 19628 KB Output is correct
15 Correct 13 ms 19664 KB Output is correct
16 Correct 11 ms 19664 KB Output is correct
17 Correct 11 ms 19680 KB Output is correct
18 Correct 11 ms 19280 KB Output is correct
19 Correct 11 ms 19264 KB Output is correct
20 Incorrect 11 ms 19664 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
21 Halted 0 ms 0 KB -