제출 #1157690

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157690		12345678	Radio Towers (IOI22_towers)	C++17	0 / 100	368 ms	12068 KiB

towers

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

using namespace std;

const int nx=1e5+5;

int n, l[nx], r[nx], rt, dpt[nx], sm;
map<int, int> mp;
stack<int> s;
vector<int> h;
set<pair<int, int>> res;

void dfs(int u, int p)
{
    if (l[u]!=-1) dfs(l[u], u), dpt[u]=max(dpt[u], dpt[l[u]]+h[u]-h[l[u]]);
    if (r[u]!=-1) dfs(r[u], u), dpt[u]=max(dpt[u], dpt[r[u]]+h[u]-h[r[u]]);
    if (p!=-1) mp[dpt[u]+1]++, mp[dpt[u]+h[p]-h[u]+1]--;
}

void init(int N, std::vector<int> H) {
    h=H;
    for (int i=0; i<N; i++)
    {
        l[i]=r[i]=-1;
        while (!s.empty()&&H[s.top()]<H[i]) l[i]=s.top(), s.pop();
        if (s.empty()) rt=i;
        else r[s.top()]=i;
        s.push(i);
    }
    dfs(rt, -1);
    for (auto [x, y]:mp) sm+=y, res.insert({x, sm});
    //for (auto x:res) cout<<x.first<<' '<<x.second<<'\n';
}

int max_towers(int L, int R, int D) {
    return prev(res.upper_bound({D, 1e9}))->second;
}

• 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