Submission #701183

#	Time	Username	Problem	Language	Result	Execution time	Memory
701183		boris_mihov	Radio Towers (IOI22_towers)	C++17	0 / 100	4097 ms	8400 KiB

towers

#include "towers.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXLOG = 20;
const int INF  = 1e9;

int n;
int h[MAXN];
int perm[MAXN];
int getLog[MAXN];

struct BIT
{
    int tree[MAXN];
    inline void update(int pos, int val)
    {
        for (int idx = pos ; idx <= n ; idx += idx & (-idx))
        {
            tree[idx] += val;
        }
    }

    inline int query(int pos)
    {
        int ans = 0;
        for (int idx = pos ; idx >= 1 ; idx -= idx & (-idx))
        {
            ans += tree[idx];
        }

        return ans;
    }

    inline int find(int k)
    {
        int pos = 0;
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (pos + (1 << log) > n) continue;
            if (tree[pos + (1 << log)] < k)
            {
                pos += (1 << log);
                k -= tree[pos];
            }
        }

        return pos + 1;
    }
};

BIT tree;

struct SparseMAX
{
    int sparse[MAXLOG][MAXN];
    void build()
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            sparse[0][i] = h[i];
        }

        for (int log = 1 ; (1 << log) <= n ; ++log)
        {
            for (int i = 1 ; i + (1 << log) - 1 <= n ; ++i)
            {
                sparse[log][i] = std::max(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
            }
        }

        for (int i = 1 ; i <= n ; ++i)
        {
            getLog[i] = getLog[i - 1];
            if ((1 << getLog[i] + 1) < i) getLog[i]++;
        }
    }

    inline int findMAX(int l, int r)
    {
        int log = getLog[r - l + 1];
        return std::max(sparse[log][l], sparse[log][r - (1 << log) + 1]);
    }
};

int firstPos;
bool first = true;
int prefix[MAXN];
SparseMAX sparse;
void init(int N, std::vector <int> H) 
{   
    n = N;
    for (int i = 0 ; i < n ; ++i)
    {
        h[i + 1] = H[i];
    }

    sparse.build();
    for (int i = 1 ; i <= n ; ++i)
    {
        prefix[i] = prefix[i - 1] + (i != 1 && i != n && h[i] < h[i - 1] && h[i] < h[i + 1]);
    }

    int where = 0;
    if (h[1] > h[2])
    {
        firstPos = 1;
        where = 1;
    }

    for (int i = 2 ; i <= n ; ++i)
    {
        if (h[i] > h[i - 1])
        {
            firstPos = i;
            where = 1;
        }

        if (h[i] < h[i - 1] && where == 1)
        {
            first = false;
            break;
        }
    }

    if (firstPos == 0)
    {
        firstPos = n;
    }
}

int max_towers(int l, int r, int d) 
{
    if (first)
    {
        if (l > firstPos || r > firstPos) return 1;
        if (std::max(h[l], h[r]) <= h[firstPos] - d) return 2;
        return 1;
    }

    if (d == 1)
    {
        if (r - l < 2) return 1;
        return prefix[r - 1] - prefix[l] + (h[l] < h[l + 1]) + (h[r] < h[r - 1]); 
    }

    l++; r++;
    std::iota(perm + l, perm + r + 1, l);
    std::sort(perm + l, perm + r + 1, [&](int x, int y)
    {
        return h[x] < h[y];
    });

    int ans = 0;
    for (int i = l ; i <= r ; ++i)
    {
        bool can = true;
        int pos = perm[i];
        
        if (tree.query(pos) != 0)
        {
            int left = tree.find(tree.query(pos));
            if (left == pos - 1 || sparse.findMAX(left + 1, pos - 1) - d < std::max(h[left], h[pos]))
            {
                can = false;
            } 
        }

        if (tree.query(pos) != ans)
        {
            int right = tree.find(tree.query(pos) + 1);
            if (right == pos + 1 || sparse.findMAX(pos + 1, right - 1) - d < std::max(h[pos], h[right]))
            {
                can = false;
            } 
        }

        if (can)
        {
            ans++;
            tree.update(pos, 1);
        }
    }

    return ans;
}

Compilation message (stderr)

towers.cpp: In member function 'void SparseMAX::build()':
towers.cpp:72:93: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   72 |                 sparse[log][i] = std::max(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
      |                                                                                         ~~~~^~~
towers.cpp:79:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   79 |             if ((1 << getLog[i] + 1) < i) getLog[i]++;
      |                       ~~~~~~~~~~^~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23