Submission #897677

#	Time	Username	Problem	Language	Result	Execution time	Memory
897677		abcvuitunggio	Radio Towers (IOI22_towers)	C++17	100 / 100	954 ms	45116 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=2e9;
int n,h[100001],a[100001],b[100001],id,r[100001],order[100001];
vector <int> ve;
struct PT{
    int sum=0,mn=INF,mx=-INF,l=0,r=0;
}t[2100001];
PT operator +(PT a, PT b){
    return {a.sum+b.sum,min(a.mn,b.mn),max(a.mx,b.mx)};
}
int update(int node, int l, int r, int i){
    id++;
    if (l==r){
        t[id]={1,l,l};
        return id;
    }
    int cur=id;
    t[cur]=t[node];
    int mid=(l+r)>>1;
    if (mid<i)
        t[cur].r=update(t[node].r,mid+1,r,i);
    else
        t[cur].l=update(t[node].l,l,mid,i);
    int x=t[cur].l,y=t[cur].r;
    t[cur]=t[t[cur].l]+t[t[cur].r];
    t[cur].l=x;
    t[cur].r=y;
    return cur;
}
PT get(int node, int l, int r, int u, int v){
    if ((l>=u&&r<=v)||!node)
        return t[node];
    int mid=(l+r)>>1;
    if (mid+1>v)
        return get(t[node].l,l,mid,u,v);
    if (mid<u)
        return get(t[node].r,mid+1,r,u,v);
    return get(t[node].l,l,mid,u,v)+get(t[node].r,mid+1,r,u,v);
}
struct T{
    int diff,diff2,mx,mn;
}st[400001];
T operator +(T a, T b){
    return {max(max(a.diff,b.diff),h[b.mx]-h[a.mn]),max(max(a.diff2,b.diff2),h[a.mx]-h[b.mn]),(h[a.mx]>h[b.mx]?a.mx:b.mx),(h[a.mn]<h[b.mn]?a.mn:b.mn)};
}
void build(int node, int l, int r){
    if (l==r){
        st[node]={0,0,l,l};
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    st[node]=st[node<<1]+st[node<<1|1];
}
int get(int node, int l, int r, int u, int v, int val){
    if (l>v||r<u||u>v||h[st[node].mx]<val)
        return -1;
    if (l==r)
        return l;
    int mid=(l+r)>>1,x=get(node<<1|1,mid+1,r,u,v,val);
    return (x!=-1?x:get(node<<1,l,mid,u,v,val));
}
int get2(int node, int l, int r, int u, int v, int val){
    if (l>v||r<u||u>v||h[st[node].mx]<val)
        return n;
    if (l==r)
        return l;
    int mid=(l+r)>>1,x=get2(node<<1,l,mid,u,v,val);
    return (x!=n?x:get2(node<<1|1,mid+1,r,u,v,val));
}
T get3(int node, int l, int r, int u, int v){
    if (l>=u&&r<=v)
        return st[node];
    int mid=(l+r)>>1;
    if (mid+1>v)
        return get3(node<<1,l,mid,u,v);
    if (mid<u)
        return get3(node<<1|1,mid+1,r,u,v);
    return get3(node<<1,l,mid,u,v)+get3(node<<1|1,mid+1,r,u,v);
}
void init(int N, vector <int> H){
    n=N;
    stack <int> st;
    for (int i=0;i<n;i++){
        h[i]=H[i];
        a[i]=b[i]=h[i];
        r[i]=n-1;
        while (!st.empty()&&h[st.top()]>h[i]){
            a[i]=max(a[i],a[st.top()]);
            int x=b[st.top()];
            st.pop();
            if (!st.empty())
                b[st.top()]=max(b[st.top()],x);
        }
        st.push(i);
    }
    while (!st.empty()&&h[st.top()]){
        int x=b[st.top()];
        st.pop();
        if (!st.empty())
            b[st.top()]=max(b[st.top()],x);
    }
    build(1,0,n-1);
    for (int i=0;i<n;i++)
        ve.push_back(min(a[i],b[i])-h[i]);
    sort(ve.begin(),ve.end());
    ve.resize(unique(ve.begin(),ve.end())-ve.begin());
    iota(order,order+n,0);
    sort(order,order+n,[](int i, int j){return min(a[i],b[i])-h[i]>min(a[j],b[j])-h[j];});
    for (int j=0;j<n;j++){
        int i=order[j];
        order[j]=lower_bound(ve.begin(),ve.end(),min(a[i],b[i])-h[i])-ve.begin();
        r[order[j]]=update((j?r[order[j-1]]:0),0,n-1,i);
    }
}
int max_towers(int L, int R, int D){
    int res=0,i,j;
    if (D<=ve.back()){
        PT tmp=get(r[lower_bound(ve.begin(),ve.end(),D)-ve.begin()],0,n-1,L,R);
        res=tmp.sum;
        i=tmp.mn;
        j=tmp.mx;
    }
    if (!res){
        i=j=get3(1,0,n-1,L,R).mn;
        res=1;
    }
    int l=get(1,0,n-1,0,i,h[i]+D),r=get2(1,0,n-1,j,n-1,h[j]+D);
    return res+(l>=L&&get3(1,0,n-1,L,l).diff>=D)+(r<=R&&get3(1,0,n-1,r,R).diff2>=D);
}

• 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