oj.uz

Submission #754638

# Submission time Handle Problem Language Result Execution time Memory
754638 2023-06-08T07:36:29 Z boris_mihov Radio Towers (IOI22_towers) C++17
35 / 100
 1419 ms 52724 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 remove = 0;
    int idx = sparse.findIDX(L, R);
    if (a[idx] < L && c[idx] > R) remove++;
    return prefix[R] - prefix[L - 1] + left.query(L, R, L) + (R - L + 1 - right.query(L, R, R + 1)) + remove;
}

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 315 ms 25204 KB Output is correct
2 Correct 799 ms 29576 KB Output is correct
3 Correct 888 ms 29616 KB Output is correct
4 Correct 824 ms 29640 KB Output is correct
5 Correct 726 ms 29832 KB Output is correct
6 Correct 954 ms 29648 KB Output is correct
7 Correct 712 ms 29764 KB Output is correct
8 Correct 13 ms 19020 KB Output is correct
9 Correct 13 ms 19288 KB Output is correct
10 Correct 11 ms 19280 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19152 KB Output is correct
2 Correct 11 ms 19664 KB Output is correct
3 Correct 12 ms 19664 KB Output is correct
4 Correct 14 ms 19608 KB Output is correct
5 Correct 12 ms 19612 KB Output is correct
6 Correct 11 ms 19664 KB Output is correct
7 Correct 12 ms 19664 KB Output is correct
8 Correct 11 ms 19296 KB Output is correct
9 Correct 11 ms 19296 KB Output is correct
10 Incorrect 11 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 10 ms 19152 KB Output is correct
2 Correct 11 ms 19664 KB Output is correct
3 Correct 12 ms 19664 KB Output is correct
4 Correct 14 ms 19608 KB Output is correct
5 Correct 12 ms 19612 KB Output is correct
6 Correct 11 ms 19664 KB Output is correct
7 Correct 12 ms 19664 KB Output is correct
8 Correct 11 ms 19296 KB Output is correct
9 Correct 11 ms 19296 KB Output is correct
10 Incorrect 11 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 1123 ms 52344 KB Output is correct
2 Correct 1416 ms 52572 KB Output is correct
3 Correct 1236 ms 52440 KB Output is correct
4 Correct 1361 ms 52456 KB Output is correct
5 Correct 1372 ms 52520 KB Output is correct
6 Correct 1281 ms 52468 KB Output is correct
7 Correct 1373 ms 52500 KB Output is correct
8 Correct 855 ms 29644 KB Output is correct
9 Correct 817 ms 29836 KB Output is correct
10 Correct 1255 ms 52484 KB Output is correct
11 Correct 1419 ms 52724 KB Output is correct
12 Correct 935 ms 29596 KB Output is correct
13 Correct 839 ms 29824 KB Output is correct
14 Correct 11 ms 19024 KB Output is correct
15 Correct 11 ms 19324 KB Output is correct
16 Correct 11 ms 19280 KB Output is correct
17 Correct 85 ms 52508 KB Output is correct
18 Correct 90 ms 52428 KB Output is correct
19 Correct 91 ms 52536 KB Output is correct
20 Correct 28 ms 29764 KB Output is correct
21 Correct 76 ms 52480 KB Output is correct
22 Correct 36 ms 29328 KB Output is correct
23 Correct 34 ms 29332 KB Output is correct
24 Correct 33 ms 29336 KB Output is correct
25 Correct 31 ms 29848 KB Output is correct
26 Correct 44 ms 29608 KB Output is correct
27 Correct 14 ms 19596 KB Output is correct
28 Correct 12 ms 19664 KB Output is correct
29 Correct 12 ms 19664 KB Output is correct
30 Correct 11 ms 19280 KB Output is correct
31 Correct 11 ms 19628 KB Output is correct
32 Correct 10 ms 19328 KB Output is correct
33 Correct 11 ms 19232 KB Output is correct
34 Correct 11 ms 19296 KB Output is correct
35 Correct 13 ms 19256 KB Output is correct
36 Correct 11 ms 19304 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 21520 KB Output is correct
2 Correct 872 ms 29328 KB Output is correct
3 Correct 1101 ms 29380 KB Output is correct
4 Correct 852 ms 29332 KB Output is correct
5 Correct 930 ms 29312 KB Output is correct
6 Correct 787 ms 29340 KB Output is correct
7 Correct 894 ms 29328 KB Output is correct
8 Correct 808 ms 29648 KB Output is correct
9 Correct 876 ms 29764 KB Output is correct
10 Correct 881 ms 29588 KB Output is correct
11 Correct 862 ms 29584 KB Output is correct
12 Correct 40 ms 29308 KB Output is correct
13 Correct 34 ms 29320 KB Output is correct
14 Correct 32 ms 29320 KB Output is correct
15 Correct 29 ms 29832 KB Output is correct
16 Correct 32 ms 29604 KB Output is correct
17 Correct 36 ms 29048 KB Output is correct
18 Correct 34 ms 29380 KB Output is correct
19 Correct 47 ms 29332 KB Output is correct
20 Correct 34 ms 29320 KB Output is correct
21 Correct 33 ms 29320 KB Output is correct
22 Correct 41 ms 29340 KB Output is correct
23 Correct 42 ms 29324 KB Output is correct
24 Correct 29 ms 29640 KB Output is correct
25 Correct 31 ms 29840 KB Output is correct
26 Correct 27 ms 29448 KB Output is correct
27 Correct 43 ms 29784 KB Output is correct
28 Correct 10 ms 19280 KB Output is correct
29 Correct 13 ms 19280 KB Output is correct
30 Correct 11 ms 19280 KB Output is correct
31 Correct 10 ms 19264 KB Output is correct
32 Correct 11 ms 19280 KB Output is correct
33 Correct 14 ms 19152 KB Output is correct
34 Correct 11 ms 19296 KB Output is correct
35 Correct 10 ms 19280 KB Output is correct
36 Correct 10 ms 19268 KB Output is correct
37 Correct 11 ms 19300 KB Output is correct
38 Correct 12 ms 19316 KB Output is correct
39 Correct 10 ms 19288 KB Output is correct
40 Correct 11 ms 19312 KB Output is correct
41 Correct 10 ms 19280 KB Output is correct
42 Correct 11 ms 19312 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 10 ms 19152 KB Output is correct
2 Correct 11 ms 19664 KB Output is correct
3 Correct 12 ms 19664 KB Output is correct
4 Correct 14 ms 19608 KB Output is correct
5 Correct 12 ms 19612 KB Output is correct
6 Correct 11 ms 19664 KB Output is correct
7 Correct 12 ms 19664 KB Output is correct
8 Correct 11 ms 19296 KB Output is correct
9 Correct 11 ms 19296 KB Output is correct
10 Incorrect 11 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 315 ms 25204 KB Output is correct
2 Correct 799 ms 29576 KB Output is correct
3 Correct 888 ms 29616 KB Output is correct
4 Correct 824 ms 29640 KB Output is correct
5 Correct 726 ms 29832 KB Output is correct
6 Correct 954 ms 29648 KB Output is correct
7 Correct 712 ms 29764 KB Output is correct
8 Correct 13 ms 19020 KB Output is correct
9 Correct 13 ms 19288 KB Output is correct
10 Correct 11 ms 19280 KB Output is correct
11 Correct 10 ms 19152 KB Output is correct
12 Correct 11 ms 19664 KB Output is correct
13 Correct 12 ms 19664 KB Output is correct
14 Correct 14 ms 19608 KB Output is correct
15 Correct 12 ms 19612 KB Output is correct
16 Correct 11 ms 19664 KB Output is correct
17 Correct 12 ms 19664 KB Output is correct
18 Correct 11 ms 19296 KB Output is correct
19 Correct 11 ms 19296 KB Output is correct
20 Incorrect 11 ms 19644 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
21 Halted 0 ms 0 KB -