Submission #1009577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009577		bachhoangxuan	Radio Towers (IOI22_towers)	C++17	17 / 100	754 ms	21344 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int maxl = 20;

int lt[maxn],rt[maxn],mn[maxn];
vector<int> edge[maxn];
vector<pair<int,int>> res;

void init(int N, std::vector<int> H){
    vector<int> v;
    for(int i=0;i<N;i++){
        while(!v.empty() && H[v.back()]<H[i]) v.pop_back();
        lt[i]=(v.empty()?-1:v.back());
        v.push_back(i);
    }
    v.clear();
    for(int i=N-1;i>=0;i--){
        while(!v.empty() && H[v.back()]<H[i]) v.pop_back();
        rt[i]=(v.empty()?-1:v.back());
        v.push_back(i);
    }
    int root=-1;
    for(int i=0;i<N;i++){
        if(lt[i]==-1 && rt[i]==-1) root=i;
        else if(lt[i]==-1 || (rt[i]!=-1 && H[rt[i]]<H[lt[i]])) edge[rt[i]].push_back(i);
        else edge[lt[i]].push_back(i);
    }
    function<void(int,int)> dfs = [&](int u,int p){
        mn[u]=u;
        for(int v:edge[u]){
            dfs(v,u);
            if(H[mn[v]]<H[mn[u]]) mn[u]=mn[v];
        }
        res.push_back({H[u]-H[mn[u]],1});
        if(p!=-1) res.push_back({H[p]-H[mn[u]],-1});
    };
    dfs(root,-1);
    sort(res.begin(),res.end());
    for(int i=1;i<(int)res.size();i++) res[i].second+=res[i-1].second;
}

int max_towers(int L, int R, int D){
    int pos=lower_bound(res.begin(),res.end(),make_pair(D,0))-res.begin()-1;
    return res[pos].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