oj.uz

Submission #755139

# Submission time Handle Problem Language Result Execution time Memory
755139 2023-06-09T12:40:00 Z boris_mihov Radio Towers (IOI22_towers) C++17
17 / 100
 1446 ms 57076 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 binaryCount(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 binaryFirst(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 == tree[node].size() ? INF : tree[node][r]);
    }

    int binaryLast(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 (l == -1 ? 0 : tree[node][l]);
    }

    int queryCount(int l, int r, int node, int queryL, int queryR, int queryValL, int queryValR)
    {
        if (queryL <= l && r <= queryR)
        {
            return binaryCount(node, queryValR) - binaryCount(node, queryValL - 1);
        }

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

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

        int res = INF;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = std::min(res, queryFirst(l, mid, 2*node, queryL, queryR, queryVal));
        if (mid + 1 <= queryR) res = std::min(res, queryFirst(mid + 1, r, 2*node + 1, queryL, queryR, queryVal));
        return res;
    }

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

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

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

    int queryCount(int to, int l, int r)
    {
        return queryCount(1, n, 1, 1, to, l, r);
    }

    int queryFirst(int to, int l)
    {
        return queryFirst(1, n, 1, 1, to, l);
    }

    int queryLast(int to, int r)
    {
        return queryLast(1, n, 1, 1, to, r);
    }
};

MST left, right;
struct SparseMAX
{
    int sparseMAX[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)
        {
            sparseMAX[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)
            {
                sparseMAX[log][i] = cmp(sparseMAX[log - 1][i], sparseMAX[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(sparseMAX[log][l], sparseMAX[log][r - (1 << log) + 1])];
    }

    int findIDX(int l, int r)
    {
        int log = lg[r - l + 1];
        return cmp(sparseMAX[log][l], sparseMAX[log][r - (1 << log) + 1]);
    }
};

struct SegmentTree
{
    struct Node
    {
        int max;
        int min;
        int maxDiffL;
        int maxDiffR;
        
        Node()
        {
            max = -1;
        }
    };

    Node combine(Node left, Node right)
    {
        if (left.max == -1)
        {
            return right;
        }

        Node res;
        res.min = std::min(left.min, right.min);
        res.max = std::max(left.max, right.max);
        res.maxDiffL = std::max(left.maxDiffL, right.maxDiffL);
        res.maxDiffR = std::max(left.maxDiffR, right.maxDiffR);
        res.maxDiffL = std::max(res.maxDiffL, right.max - left.min);
        res.maxDiffR = std::max(res.maxDiffR, left.max - right.min);
        return res;
    }

    Node tree[4*MAXN];
    void build(int l, int r, int node, int vals[])
    {
        if (l == r)
        {
            tree[node].min = vals[l];
            tree[node].max = vals[l];
            tree[node].maxDiffL = 0;
            tree[node].maxDiffR = 0;
            return;
        }

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

    Node query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

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

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

    int queryL(int l, int r)
    {
        return query(1, n, 1, l, r).maxDiffL;
    }

    int queryR(int l, int r)
    {
        return query(1, n, 1, l, r).maxDiffR;
    }
};

int a[MAXN];
int b[MAXN];
int c[MAXN];
int d[MAXN];
int h[MAXN];
int perm[MAXN];
int cost[MAXN];
SparseMAX sparseMAX;
SegmentTree maxDiff;
std::stack <int> st;
std::vector <int> v;
MST tree;

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

    sparseMAX.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] = sparseMAX.findMAX(a[i] + 1, i - 1) - h[i];
        }

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

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

    std::iota(perm + 1, perm + 1 + n, 1);
    std::sort(perm + 1, perm + 1 + n, [&](const int &x, const int &y)
    {
        return cost[x] > cost[y];
    });

    tree.build(perm);
    maxDiff.build(h);
}

int aaa;
int max_towers(int L, int R, int D) 
{
    L++; R++;
    int l = 0, r = n + 1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (cost[perm[mid]] >= D) l = mid;
        else r = mid;
    }

    if (l == 0)
    {
        return 1;
    }

    int cnt = tree.queryCount(l, L, R);
    if (++aaa == 12)
    {
        return cnt;
    }
    
    if (cnt == 0)
    {
        return 1;
    }

    int first = tree.queryFirst(l, L);
    int last = tree.queryLast(l, R);

    l = L, r = first;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (sparseMAX.findMAX(mid, first - 1) < h[first] + D) r = mid;
        else l = mid;
    }

    if (maxDiff.queryL(L, l) >= D)
    {
        cnt++;
    }

    l = last, r = R;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (sparseMAX.findMAX(last + 1, mid) < h[last] + D) l = mid;
        else r = mid;
    }

    if (maxDiff.queryR(r, R) >= D)
    {
        cnt++;
    }

    return cnt;
}

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 'int MST::binaryFirst(int, int)':
towers.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         return (r == tree[node].size() ? INF : tree[node][r]);
      |                 ~~^~~~~~~~~~~~~~~~~~~~
towers.cpp: In member function 'void SparseMAX::build(int*)':
towers.cpp:182:97: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  182 |                 sparseMAX[log][i] = cmp(sparseMAX[log - 1][i], sparseMAX[log - 1][i + (1 << log - 1)]);
      |                                                                                             ~~~~^~~
towers.cpp:189:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  189 |             if ((1 << lg[i] + 1) < i)
      |                       ~~~~~~^~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 371 ms 47608 KB 12th lines differ - on the 1st token, expected: '2', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 34860 KB Output is correct
2 Correct 20 ms 35152 KB Output is correct
3 Correct 19 ms 35152 KB Output is correct
4 Correct 19 ms 35060 KB Output is correct
5 Correct 21 ms 35088 KB Output is correct
6 Correct 20 ms 35052 KB Output is correct
7 Correct 23 ms 35152 KB Output is correct
8 Correct 18 ms 35152 KB Output is correct
9 Correct 18 ms 35152 KB Output is correct
10 Correct 18 ms 35148 KB Output is correct
11 Correct 20 ms 35152 KB Output is correct
12 Incorrect 17 ms 34796 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 34860 KB Output is correct
2 Correct 20 ms 35152 KB Output is correct
3 Correct 19 ms 35152 KB Output is correct
4 Correct 19 ms 35060 KB Output is correct
5 Correct 21 ms 35088 KB Output is correct
6 Correct 20 ms 35052 KB Output is correct
7 Correct 23 ms 35152 KB Output is correct
8 Correct 18 ms 35152 KB Output is correct
9 Correct 18 ms 35152 KB Output is correct
10 Correct 18 ms 35148 KB Output is correct
11 Correct 20 ms 35152 KB Output is correct
12 Incorrect 17 ms 34796 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1067 ms 56512 KB Output is correct
2 Correct 1446 ms 56644 KB Output is correct
3 Correct 1302 ms 56684 KB Output is correct
4 Correct 1149 ms 56644 KB Output is correct
5 Correct 1079 ms 56636 KB Output is correct
6 Correct 1032 ms 56708 KB Output is correct
7 Correct 1348 ms 56620 KB Output is correct
8 Incorrect 893 ms 56704 KB 12th lines differ - on the 1st token, expected: '1', found: '0'
9 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 39696 KB Output is correct
2 Correct 1034 ms 56648 KB Output is correct
3 Correct 1189 ms 56628 KB Output is correct
4 Correct 1116 ms 56688 KB Output is correct
5 Correct 1083 ms 56656 KB Output is correct
6 Correct 1294 ms 56652 KB Output is correct
7 Correct 1200 ms 56648 KB Output is correct
8 Correct 930 ms 56620 KB Output is correct
9 Correct 1055 ms 57012 KB Output is correct
10 Correct 996 ms 56724 KB Output is correct
11 Correct 1029 ms 56776 KB Output is correct
12 Correct 71 ms 56656 KB Output is correct
13 Correct 76 ms 56628 KB Output is correct
14 Correct 76 ms 56680 KB Output is correct
15 Correct 68 ms 57056 KB Output is correct
16 Correct 67 ms 56632 KB Output is correct
17 Correct 70 ms 55936 KB Output is correct
18 Correct 75 ms 56644 KB Output is correct
19 Correct 75 ms 56624 KB Output is correct
20 Correct 75 ms 56648 KB Output is correct
21 Correct 94 ms 56816 KB Output is correct
22 Correct 74 ms 56680 KB Output is correct
23 Correct 75 ms 56644 KB Output is correct
24 Correct 66 ms 56632 KB Output is correct
25 Correct 63 ms 57032 KB Output is correct
26 Correct 65 ms 56708 KB Output is correct
27 Correct 64 ms 57076 KB Output is correct
28 Correct 19 ms 35084 KB Output is correct
29 Correct 20 ms 35280 KB Output is correct
30 Correct 21 ms 35104 KB Output is correct
31 Correct 19 ms 35068 KB Output is correct
32 Correct 19 ms 35152 KB Output is correct
33 Correct 19 ms 34896 KB Output is correct
34 Correct 19 ms 35088 KB Output is correct
35 Correct 19 ms 35152 KB Output is correct
36 Correct 20 ms 35120 KB Output is correct
37 Correct 20 ms 35152 KB Output is correct
38 Correct 20 ms 35064 KB Output is correct
39 Correct 19 ms 35164 KB Output is correct
40 Correct 19 ms 35152 KB Output is correct
41 Correct 19 ms 35116 KB Output is correct
42 Correct 20 ms 35152 KB Output is correct
43 Correct 20 ms 35136 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 34860 KB Output is correct
2 Correct 20 ms 35152 KB Output is correct
3 Correct 19 ms 35152 KB Output is correct
4 Correct 19 ms 35060 KB Output is correct
5 Correct 21 ms 35088 KB Output is correct
6 Correct 20 ms 35052 KB Output is correct
7 Correct 23 ms 35152 KB Output is correct
8 Correct 18 ms 35152 KB Output is correct
9 Correct 18 ms 35152 KB Output is correct
10 Correct 18 ms 35148 KB Output is correct
11 Correct 20 ms 35152 KB Output is correct
12 Incorrect 17 ms 34796 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 371 ms 47608 KB 12th lines differ - on the 1st token, expected: '2', found: '0'
2 Halted 0 ms 0 KB -