Submission #633469

#	Time	Username	Problem	Language	Result	Execution time	Memory
633469		Lawliet	Radio Towers (IOI22_towers)	C++17	0 / 100	541 ms	8100 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

const int maxl = 20;
const int maxn = 100010;
const int inf = 1000000010;

class SparseTable
{
    public:

        void build(int n, vector<int> v, bool mn = false)
        {
            isMin = mn;

            for(int i = 1 ; i <= n ; i++)
                tab[0][i] = (mn ? -v[i] : v[i]);

            for(int k = 1 ; k < maxl ; k++)
                for(int i = 1 ; i + (1 << k) - 1 <= n ; i++)
                    tab[k][i] = max( tab[k - 1][i] , tab[k - 1][i + (1 << (k - 1))] ); 
        }

        int query(int l, int r)
        {
            if( l > r )
                return (isMin ? inf : -inf);

            int t = 31 - __builtin_clz(r - l + 1);
            int ans = max( tab[t][l] , tab[t][r - (1 << t) + 1] );

            return (isMin ? -ans : ans);
        }

    protected:

        bool isMin;
        int tab[maxl][maxn];
};

int n;

int v[maxn];

SparseTable stV;

vector<int> ans;
vector<int> valleys;

void findValleys()
{
    v[0] = v[n + 1] = inf;

    for(int i = 1 ; i <= n ; i++)
        if( v[i - 1] > v[i] && v[i] < v[i + 1] ) valleys.push_back( i );

    for(int i = 0 ; i < (int)valleys.size() - 1 ; i++)
    {
        int peak = stV.query( valleys[i] + 1 , valleys[i + 1] - 1 );
        int diff = min( peak - v[ valleys[i] ] , peak - v[ valleys[i + 1] ] );

        ans.push_back( diff );
    }
}

void init(int N, vector<int> H) {
    n = N;

    H.insert( H.begin() , 0 );

    stV.build( n , H );

    for(int i = 1 ; i <= n ; i++)
        v[i] = H[i];

    findValleys();
}

int max_towers(int L, int R, int D) 
{
    int t = upper_bound( ans.begin() , ans.end() , D ) - ans.begin();
    return t + 1;
}

• 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