Submission #1175097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175097		12345678	Radio Towers (IOI22_towers)	C++17	100 / 100	614 ms	42604 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};
vector<pair<int, int>> srt;

struct persistsegtree
{
    struct node
    {
        int sm;
        node *l, *r;
        node(int sm=0): sm(sm), l(l), r(r){} 
    };
    typedef node* pnode;
    pnode rt[nx];
    void build(int l, int r, pnode &k)
    {
        k=new node();
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md ,k->l);
        build(md+1, r, k->r);
    }
    void update(int l, int r, pnode &k, pnode p, int idx)
    {
        k=new node(*p);
        if (l==r) return k->sm++, void();
        int md=(l+r)/2;
        if (idx<=md) update(l, md, k->l, p->l, idx);
        else update(md+1, r, k->r, p->r, idx);
        k->sm=k->l->sm+k->r->sm;
    }
    int getsum(int l, int r, pnode k, int ql, int qr)
    {
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return k->sm;
        int md=(l+r)/2;
        return getsum(l, md, k->l, ql, qr)+getsum(md+1, r, k->r, ql, qr);
    }
    int getfirstleft(int l, int r, pnode k, int idx)
    {
        if (idx<l||k->sm==0) return 0;
        if (l==r) return l;
        int md=(l+r)/2;
        int rvl=getfirstleft(md+1, r, k->r, idx);
        return rvl?rvl:getfirstleft(l, md, k->l, idx);
    }
    int getfirstright(int l, int r, pnode k, int idx)
    {
        if (r<idx||k->sm==0) return 0;
        if (l==r) return l;
        int md=(l+r)/2;
        int lvl=getfirstright(l, md, k->l, idx);
        return lvl?lvl:getfirstright(md+1, r, k->r, idx);
    }
} p;

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 l;
        int md=(l+r)/2;
        int rvl=getlessleft(md+1, r, 2*i+1, idx, vl);
        return rvl?rvl:getlessleft(l, md, 2*i, idx, vl);
    }
    int getgreaterleft(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||d[i].mx<vl) return 0;
        if (l==r) return l;
        int md=(l+r)/2;
        int rvl=getgreaterleft(md+1, r, 2*i+1, idx, vl);
        return rvl?rvl:getgreaterleft(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 l;
        int md=(l+r)/2;
        int lvl=getlessright(l, md, 2*i, idx, vl);
        return lvl?lvl:getlessright(md+1, r, 2*i+1, idx, vl);
    }
    int getgreaterright(int l, int r, int i, int idx, int vl)
    {
        if(r<idx||d[i].mx<vl) return 0;
        if (l==r) return l;
        int md=(l+r)/2;
        int lvl=getgreaterright(l, md, 2*i, idx, vl);
        return lvl?lvl:getgreaterright(md+1, r, 2*i+1, idx, vl);
    }
    node getmaxdif(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return node();
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return merge(getmaxdif(l, md, 2*i, ql, qr), getmaxdif(md+1, r, 2*i+1, ql, qr));
    }
} 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) srt.push_back({min(s.getmax(1, n, 1, cl+1, i-1), s.getmax(1, n, 1, i+1, cr-1))-h[i], i});
            else if (cr) srt.push_back({s.getmax(1, n, 1, i+1, cr-1)-h[i], i});
            else if (cl) srt.push_back({s.getmax(1, n, 1, cl+1, i-1)-h[i], i});
            else srt.push_back({2e9, i});
        }
    }
    sort(srt.begin(), srt.end());
    p.build(1, n, p.rt[srt.size()]);
    for (int i=srt.size()-1; i>=0; i--) p.update(1, n, p.rt[i], p.rt[i+1], srt[i].second);
}

int max_towers(int L, int R, int D) {
    L++, R++;
    int idx=lower_bound(srt.begin(), srt.end(), make_pair(D, 0))-srt.begin();
    int curans=p.getsum(1, n, p.rt[idx], L, R);
    if (curans==0)
    {
        auto tmp=s.getmaxdif(1, n, 1, L, R);
        if (tmp.difl>=D&&tmp.difr>=D) return 2;
        else return 1;
    }
    int lidx=p.getfirstright(1, n, p.rt[idx], L);
    if (s.getmax(1, n, 1, L, lidx)>=h[lidx]+D)
    {
        int tidx=s.getgreaterleft(1, n, 1, lidx, h[lidx]+D);
        if (s.getmaxdif(1, n, 1, L, tidx).difl>=D) curans++;
    }
    int ridx=p.getfirstleft(1, n, p.rt[idx], R);
    if (s.getmax(1, n, 1, ridx, R)>=h[ridx]+D)
    {
        int tidx=s.getgreaterright(1, n, 1, ridx, h[ridx]+D);
        if (s.getmaxdif(1, n, 1, tidx, R).difr>=D) curans++;
    }
    return curans;
}

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