제출 #755150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
755150		boris_mihov	송신탑 (IOI22_towers)	C++17	100 / 100	2193 ms	57120 KiB

towers

#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 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 (cnt == 0)
    {
        l = L - 1;
        r = R + 1;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (maxDiff.queryL(L, mid) >= D && maxDiff.queryR(mid, R) >= D)
            {
                return 2;
            }

            if (maxDiff.queryL(L, mid) < D) l = mid;
            else r = mid;
        }

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

컴파일 시 표준 에러 (stderr) 메시지

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: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19
• Subtask 7: 23 / 23