oj.uz

Submission #754642

# Submission time Handle Problem Language Result Execution time Memory
754642 2023-06-08T07:39:22 Z boris_mihov Radio Towers (IOI22_towers) C++17
35 / 100
 1368 ms 52604 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 && c[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 341 ms 25160 KB Output is correct
2 Correct 718 ms 29700 KB Output is correct
3 Correct 908 ms 29576 KB Output is correct
4 Correct 753 ms 29712 KB Output is correct
5 Correct 785 ms 29848 KB Output is correct
6 Correct 689 ms 29636 KB Output is correct
7 Correct 737 ms 29852 KB Output is correct
8 Correct 11 ms 19024 KB Output is correct
9 Correct 12 ms 19244 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 9 ms 19152 KB Output is correct
2 Correct 13 ms 19616 KB Output is correct
3 Correct 10 ms 19664 KB Output is correct
4 Correct 13 ms 19664 KB Output is correct
5 Correct 12 ms 19616 KB Output is correct
6 Correct 11 ms 19604 KB Output is correct
7 Correct 12 ms 19632 KB Output is correct
8 Correct 10 ms 19280 KB Output is correct
9 Correct 12 ms 19268 KB Output is correct
10 Incorrect 12 ms 19644 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 9 ms 19152 KB Output is correct
2 Correct 13 ms 19616 KB Output is correct
3 Correct 10 ms 19664 KB Output is correct
4 Correct 13 ms 19664 KB Output is correct
5 Correct 12 ms 19616 KB Output is correct
6 Correct 11 ms 19604 KB Output is correct
7 Correct 12 ms 19632 KB Output is correct
8 Correct 10 ms 19280 KB Output is correct
9 Correct 12 ms 19268 KB Output is correct
10 Incorrect 12 ms 19644 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 1052 ms 52356 KB Output is correct
2 Correct 1214 ms 52436 KB Output is correct
3 Correct 1298 ms 52436 KB Output is correct
4 Correct 1043 ms 52448 KB Output is correct
5 Correct 1107 ms 52524 KB Output is correct
6 Correct 1368 ms 52476 KB Output is correct
7 Correct 1157 ms 52536 KB Output is correct
8 Correct 913 ms 29700 KB Output is correct
9 Correct 849 ms 29828 KB Output is correct
10 Correct 1149 ms 52496 KB Output is correct
11 Correct 1162 ms 52604 KB Output is correct
12 Correct 924 ms 29604 KB Output is correct
13 Correct 726 ms 29836 KB Output is correct
14 Correct 11 ms 19024 KB Output is correct
15 Correct 11 ms 19280 KB Output is correct
16 Correct 12 ms 19280 KB Output is correct
17 Correct 88 ms 52444 KB Output is correct
18 Correct 85 ms 52492 KB Output is correct
19 Correct 87 ms 52528 KB Output is correct
20 Correct 30 ms 29836 KB Output is correct
21 Correct 79 ms 52496 KB Output is correct
22 Correct 36 ms 29344 KB Output is correct
23 Correct 33 ms 29332 KB Output is correct
24 Correct 34 ms 29320 KB Output is correct
25 Correct 29 ms 29764 KB Output is correct
26 Correct 29 ms 29596 KB Output is correct
27 Correct 12 ms 19644 KB Output is correct
28 Correct 11 ms 19664 KB Output is correct
29 Correct 11 ms 19664 KB Output is correct
30 Correct 11 ms 19280 KB Output is correct
31 Correct 11 ms 19664 KB Output is correct
32 Correct 11 ms 19324 KB Output is correct
33 Correct 11 ms 19280 KB Output is correct
34 Correct 11 ms 19280 KB Output is correct
35 Correct 11 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 345 ms 21484 KB Output is correct
2 Correct 811 ms 29316 KB Output is correct
3 Correct 897 ms 29380 KB Output is correct
4 Correct 929 ms 29324 KB Output is correct
5 Correct 668 ms 29352 KB Output is correct
6 Correct 848 ms 29352 KB Output is correct
7 Correct 781 ms 29432 KB Output is correct
8 Correct 794 ms 29640 KB Output is correct
9 Correct 1020 ms 29764 KB Output is correct
10 Correct 687 ms 29568 KB Output is correct
11 Correct 1018 ms 29648 KB Output is correct
12 Correct 34 ms 29320 KB Output is correct
13 Correct 41 ms 29400 KB Output is correct
14 Correct 33 ms 29420 KB Output is correct
15 Correct 31 ms 29824 KB Output is correct
16 Correct 31 ms 29472 KB Output is correct
17 Correct 34 ms 29076 KB Output is correct
18 Correct 34 ms 29308 KB Output is correct
19 Correct 34 ms 29380 KB Output is correct
20 Correct 36 ms 29352 KB Output is correct
21 Correct 40 ms 29344 KB Output is correct
22 Correct 44 ms 29328 KB Output is correct
23 Correct 46 ms 29384 KB Output is correct
24 Correct 41 ms 29600 KB Output is correct
25 Correct 39 ms 29732 KB Output is correct
26 Correct 31 ms 29476 KB Output is correct
27 Correct 30 ms 29844 KB Output is correct
28 Correct 11 ms 19320 KB Output is correct
29 Correct 11 ms 19280 KB Output is correct
30 Correct 11 ms 19268 KB Output is correct
31 Correct 11 ms 19280 KB Output is correct
32 Correct 11 ms 19280 KB Output is correct
33 Correct 11 ms 19224 KB Output is correct
34 Correct 11 ms 19280 KB Output is correct
35 Correct 11 ms 19280 KB Output is correct
36 Correct 11 ms 19280 KB Output is correct
37 Correct 11 ms 19280 KB Output is correct
38 Correct 11 ms 19280 KB Output is correct
39 Correct 11 ms 19280 KB Output is correct
40 Correct 11 ms 19280 KB Output is correct
41 Correct 11 ms 19280 KB Output is correct
42 Correct 11 ms 19280 KB Output is correct
43 Correct 11 ms 19280 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19152 KB Output is correct
2 Correct 13 ms 19616 KB Output is correct
3 Correct 10 ms 19664 KB Output is correct
4 Correct 13 ms 19664 KB Output is correct
5 Correct 12 ms 19616 KB Output is correct
6 Correct 11 ms 19604 KB Output is correct
7 Correct 12 ms 19632 KB Output is correct
8 Correct 10 ms 19280 KB Output is correct
9 Correct 12 ms 19268 KB Output is correct
10 Incorrect 12 ms 19644 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 341 ms 25160 KB Output is correct
2 Correct 718 ms 29700 KB Output is correct
3 Correct 908 ms 29576 KB Output is correct
4 Correct 753 ms 29712 KB Output is correct
5 Correct 785 ms 29848 KB Output is correct
6 Correct 689 ms 29636 KB Output is correct
7 Correct 737 ms 29852 KB Output is correct
8 Correct 11 ms 19024 KB Output is correct
9 Correct 12 ms 19244 KB Output is correct
10 Correct 10 ms 19280 KB Output is correct
11 Correct 9 ms 19152 KB Output is correct
12 Correct 13 ms 19616 KB Output is correct
13 Correct 10 ms 19664 KB Output is correct
14 Correct 13 ms 19664 KB Output is correct
15 Correct 12 ms 19616 KB Output is correct
16 Correct 11 ms 19604 KB Output is correct
17 Correct 12 ms 19632 KB Output is correct
18 Correct 10 ms 19280 KB Output is correct
19 Correct 12 ms 19268 KB Output is correct
20 Incorrect 12 ms 19644 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
21 Halted 0 ms 0 KB -