제출 #1175085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175085		12345678	Radio Towers (IOI22_towers)	C++17	0 / 100	23 ms	10328 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}, upd[nx];

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 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);
    }
} 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) upd[min(s.getmax(1, n, 1, cl+1, i-1), s.getmax(1, n, 1, i+1, cr-1))-h[i]].push_back(i);
            else if (cr) upd[s.getmax(1, n, 1, i+1, cr-1)-h[i]].push_back(i);
            else if (cl) upd[s.getmax(1, n, 1, cl+1, i-1)-h[i]].push_back(i);
            else upd[n].push_back(i);
        }
    }
    p.build(1, n, p.rt[n+1]);
    for (int i=n; i>=1; i--)
    {
        p.rt[i]=p.rt[i+1];
        for (auto idx:upd[i]) p.update(1, n, p.rt[i], p.rt[i], idx);
    }
}

int max_towers(int L, int R, int D) {
    if (D>n) return 1;
    return p.getsum(1, n, p.rt[D], 1, n);
}

• 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