제출 #1175077

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

towers

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

using namespace std;

const int nx=1e5+5;

int n, vl[nx];
vector<int> h={0}, srt;

struct segtree
{
    struct node
    {
        int mx, mn, difl, difr;
        node(int mx=0, int mn=1e9, int difl=0, int difr=0): mx(mx), mn(mn), difl(difl), difr(difr){}
    } d[4*nx];
    node merge(node &l, node &r)
    {
        node res;
        res.mx=max(l.mx, r.mx);
        res.mn=min(l.mn, r.mn);
        res.difl=max({l.difl, r.difl, r.mx-l.mn});
        res.difr=max({l.difr, r.difr, l.mx-r.mn});
        return res;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return d[i]=node(h[l], h[l]), void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    int getmax(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return d[i].mx;
        int md=(l+r)/2;
        return max(getmax(l, md, 2*i, ql, qr), getmax(md+1, r, 2*i+1, ql, qr));
    }
    int getlessleft(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||d[i].mn>=vl) return 0;
        if (l==r) return d[i].mn<vl?l:0;
        int md=(l+r)/2;
        int lvl=getlessleft(md+1, r, 2*i+1, idx, vl);
        return lvl?lvl:getlessleft(l, md, 2*i, idx, vl);
    }
    int getlessright(int l, int r, int i, int idx, int vl)
    {
        if (r<idx||d[i].mn>=vl) return 0;
        if (l==r) return d[i].mn<vl?l:0;
        int md=(l+r)/2;
        int rvl=getlessright(l, md, 2*i, idx, vl);
        return rvl?rvl:getlessright(md+1, r, 2*i+1, idx, vl);
    }
} s;

void init(int N, std::vector<int> H) {
    n=N;
    for (int i=0; i<n;i ++) h.push_back(H[i]);
    s.build(1, n, 1);
    for (int i=1; i<=n; i++)
    {
        int cl=s.getlessleft(1, n, 1, i, h[i]), cr=s.getlessright(1, n, 1, i, h[i]), f=0;
        if (cl&&cl+1==i) f=1;
        if (cr&&cr-1==i) f=1;
        if (!f)
        {
            if (cl&&cr) vl[i]=min(s.getmax(1, n, 1, cl+1, i-1), s.getmax(1, n, 1, i+1, cr-1));
            else if (cr) vl[i]=s.getmax(1, n, 1, i+1, cr-1)-h[i];
            else if (cl) vl[i]=s.getmax(1, n, 1, cl+1, i-1)-h[i];
            else vl[i]=2e9;
        }
        //cout<<"debug "<<i<<' '<<h[i]<<' '<<cl<<' '<<cr<<' '<<vl[i]<<'\n';
        if (vl[i]) srt.push_back(vl[i]);
    }
    sort(srt.begin(), srt.end());
}

int max_towers(int L, int R, int D) {
    return srt.end()-lower_bound(srt.begin(), srt.end(), D);
}

• 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