제출 #1157693

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157693		12345678	송신탑 (IOI22_towers)	C++17	40 / 100	333 ms	19884 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, f;
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;
}

int max_towers(int L, int R, int D) {
    if (!f)
    {
        f=1;
        for (int i=L; i<=R; 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});
    }
    if (prev(res.upper_bound({D, 1e9}))->second) return prev(res.upper_bound({D, 1e9}))->second;
    return 1;
}

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