Submission #633479

#	Time	Username	Problem	Language	Result	Execution time	Memory
633479		Lawliet	Radio Towers (IOI22_towers)	C++17	17 / 100	945 ms	12736 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];
int ord[maxn];

SparseTable stV;

vector<int> valleys;

map<int,int> ans;

pair<int,int> getCost(int i, int j)
{
    int peak = stV.query( i + 1 , j - 1 );
    int diff = min( peak - v[i] , peak - v[j] );

    return {diff, i};
}

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

    int num = (int)valleys.size();

    iota( ord , ord + num , 0 );
    sort( ord , ord + num , [&](int i, int j){
        return v[ valleys[i] ] > v[ valleys[j] ];
    });

    multiset<pair<int,int>> allDiffs;

    for(int i = 0 ; i < (int)valleys.size() - 1 ; i++)
        allDiffs.insert( getCost( valleys[i] , valleys[i + 1] ) );

    set<int> alive;

    for(int a: valleys)
        alive.insert( a );

    for(int i = 0 ; i < num - 1 ; i++)
    {
        int t = allDiffs.begin()->first;
        ans[t] = max( ans[t] , num - i );

        int A = allDiffs.begin()->second;
        int B = *alive.upper_bound(A);

        int die = (v[A] < v[B] ? B : A);

        auto it = alive.find(die);
        auto tmp = alive.begin();

        if( it != alive.begin() )
        {
            tmp = it; tmp--;
            allDiffs.erase( allDiffs.find( getCost(*tmp, *it) ) );
        }

        tmp = it; tmp++;

        if( tmp != alive.end() )
            allDiffs.erase( allDiffs.find( getCost( *it , *tmp ) ) );

        alive.erase(die);
        it = alive.lower_bound(die);

        if( it != alive.end() && it != alive.begin() )
        {
            tmp = it; tmp--;
            allDiffs.insert( getCost(*tmp, *it) );
        }
    }
}

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) 
{
    auto t = ans.lower_bound(D);

    if( t == ans.end() )
        return 1;

    return t->second;
}

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