Submission #701178

#	Time	Username	Problem	Language	Result	Execution time	Memory
701178		boris_mihov	Radio Towers (IOI22_towers)	C++17	11 / 100	4096 ms	1568 KiB

towers

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

const int MAXN = 100000 + 10;
const int INF  = 1e9;

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

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

bool used[MAXN];
int max_towers(int l, int r, int d) 
{
    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)
    {
        int max = -1;
        bool can = true;
        int pos = perm[i];
        for (int j = pos - 1 ; j >= l && can ; --j)
        {
            if (used[j])
            {
                if (max - d < std::max(h[j], h[pos]))
                {
                    can = false;
                } else
                {
                    break;
                }
            }

            max = std::max(max, h[j]);
        }

        max = -1;
        for (int j = pos + 1 ; j <= r && can ; ++j)
        {
            if (used[j])
            {
                if (max - d < std::max(h[j], h[pos]))
                {
                    can = false;
                } else
                {
                    break;
                }
            }

            max = std::max(max, h[j]);
        }

        if (can)
        {
            ans++;
            used[pos] = true;
        }
    }

    return ans;
}

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