Submission #787139

#	Time	Username	Problem	Language	Result	Execution time	Memory
787139		alexander707070	Radio Towers (IOI22_towers)	C++17	56 / 100	4096 ms	7344 KiB

towers

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

const long long inf=1e16;
 
int n,h[MAXN],maxh,num,delta,from[MAXN],to[MAXN],border,maxdelta[MAXN];
int dp[MAXN],ans,pref[MAXN],se,te;
 
pair<int,int> tree[4*MAXN];
int mins[4*MAXN];
 
pair<int,int> combine(pair<int,int> fr,pair<int,int> sc){
    if(fr.first>sc.first)return fr;
    return sc;
}
 
void build(int v,int l,int r){
    if(l==r){
        tree[v]={h[l],l};
        mins[v]=h[l];
    }else{
        int tt=(l+r)/2;
        build(2*v,l,tt);
        build(2*v+1,tt+1,r);
        tree[v]=combine(tree[2*v],tree[2*v+1]);
        mins[v]=min(mins[2*v],mins[2*v+1]);
    }
}
 
pair<int,int> best(int v,int l,int r,int ll,int rr){
    if(ll>rr)return {-1,0};
    if(l==ll and r==rr){
        return tree[v];
    }else{
        int tt=(l+r)/2;
        return combine( best(2*v,l,tt,ll,min(tt,rr)) , best(2*v+1,tt+1,r,max(tt+1,ll),rr) );
    }
}
 
int minh(int v,int l,int r,int ll,int rr){
    if(ll>rr)return 1000000000;
    if(l==ll and r==rr){
        return mins[v];
    }else{
        int tt=(l+r)/2;
        return min( minh(2*v,l,tt,ll,min(tt,rr)) , minh(2*v+1,tt+1,r,max(tt+1,ll),rr) );
    }
}

vector<int> st,poss,lt,rt;
 
void calc(){
    for(int i=1;i<=n;i++){
        while(!st.empty() and h[i]>h[st.back()]){
            st.pop_back();
        }
        st.push_back(i);

        int l=-1,r=st.size(),tt;
        while(l+1<r){
            tt=(l+r)/2;
            if(h[st[tt]]>=h[i]+delta){
                l=tt;
            }else{
                r=tt;
            }
        }

        if(l!=-1 and minh(1,0,n+1,st[l],i)>=h[i])from[i]=st[l];
        else from[i]=0;
    }

    while(!st.empty())st.pop_back();

    for(int i=n;i>=1;i--){
        while(!st.empty() and h[i]>h[st.back()]){
            st.pop_back();
        }
        st.push_back(i);

        int l=-1,r=st.size(),tt;
        while(l+1<r){
            tt=(l+r)/2;
            if(h[st[tt]]>=h[i]+delta){
                l=tt;
            }else{
                r=tt;
            }
        }
        if(l!=-1 and minh(1,0,n+1,i,st[l])>=h[i])to[i]=st[l];
        else to[i]=n+1;
    }

    for(int i=1;i<=n;i++){
        if(from[i]>=1 and to[i]<=n){
            poss.push_back(i);
        }
        if(to[i]<=n)lt.push_back(i);
        if(from[i]>=1)rt.push_back(i);
    }
}

void calc2(){
    for(int i=1;i<=n;i++)maxdelta[i]=inf;

    for(int i=0;i<=n;i++){
        while(!st.empty() and h[i]>h[st.back()]){
            st.pop_back();
        }
        st.push_back(i);

        int l=-1,r=st.size(),tt;
        while(l+1<r){
            tt=(l+r)/2;
            if(minh(1,0,n+1,st[tt],i)>=h[i]){
                r=tt;
            }else{
                l=tt;
            }
        }


        maxdelta[i]=min(maxdelta[i],h[st[r]]-h[i]);
    }
    while(!st.empty())st.pop_back();

    for(int i=n+1;i>=1;i--){
        while(!st.empty() and h[i]>h[st.back()]){
            st.pop_back();
        }
        st.push_back(i);

        int l=-1,r=st.size(),tt;
        while(l+1<r){
            tt=(l+r)/2;
            if(minh(1,0,n+1,i,st[tt])>=h[i]){
                r=tt;
            }else{
                l=tt;
            }
        }
        
        maxdelta[i]=min(maxdelta[i],h[st[r]]-h[i]);
    }
    while(!st.empty())st.pop_back();

    sort(maxdelta+1,maxdelta+n+1);
}

void init(int N,vector<int> H){
    n=N;
    for(int i=1;i<=n;i++){
        h[i]=H[i-1];
    }
    h[0]=h[n+1]=1000000000;

    build(1,0,n+1);
    calc2();
}
 
int solve(int l,int r,int maxh,int d){
    if(l>r)return 0;
 
    int pos=best(1,0,n+1,l,r).second;
 
    int z=0;
    if(minh(1,0,n+1,l,r)<=maxh)z=1;
 
    return max(z, solve(l,pos-1,h[pos]-d,d)+solve(pos+1,r,h[pos]-d,d) );
}
 
int max_towers(int L, int R, int D){
    if(delta==0){
        delta=D;
        calc();
    }

    L++; R++;
    if(D==delta){
        ans=0;

        int l=-1,r=poss.size(),tt;
        while(l+1<r){
            tt=(l+r)/2;
            if(from[poss[tt]]>=L){
                r=tt;
            }else{
                l=tt;
            }
        }
        se=r;

        l=-1; r=poss.size();
        while(l+1<r){
            tt=(l+r)/2;
            if(to[poss[tt]]<=R){
                l=tt;
            }else{
                r=tt;
            }
        }
        te=l;

        if(se<=te)ans+=te-se+1;

        if(se==poss.size())se=R+1;
        else se=poss[se];

        if(te==-1)te=L-1;
        else te=poss[te];

        l=-1; r=lt.size();
        while(l+1<r){
            tt=(l+r)/2;
            if(lt[tt]>=L){
                r=tt;
            }else{
                l=tt;
            }
        }

        border=-1;
        if(r!=lt.size() and to[lt[r]]<se){
            border=to[lt[r]]; ans++;
        }

        l=-1; r=rt.size();
        while(l+1<r){
            tt=(l+r)/2;
            if(rt[tt]<=R){
                l=tt;
            }else{
                r=tt;
            }
        }
        if(l!=-1 and from[rt[l]]>=max(border,te+1))ans++;

        if(ans==0)ans++;

        return ans;   
    }

    if(L==1 and R==n){
        int l=0,r=n+1,tt;
        while(l+1<r){
            tt=(l+r)/2;
            if(maxdelta[tt]>=D){
                r=tt;
            }else{
                l=tt;
            }
        }
        return n-r+1;
    }

    return solve(L,R,1000000000,D);
}
 
/*
int main(){
    init(7, {10, 20, 60, 40, 50, 30, 70});
    cout<<max_towers(1,5,10)<<"\n";
    cout<<max_towers(0, 6, 17)<<"\n";
}
*/

Compilation message (stderr)

towers.cpp: In function 'void calc2()':
towers.cpp:105:38: warning: overflow in conversion from 'long long int' to 'int' changes value from '10000000000000000' to '1874919424' [-Woverflow]
  105 |     for(int i=1;i<=n;i++)maxdelta[i]=inf;
      |                                      ^~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:207:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |         if(se==poss.size())se=R+1;
      |            ~~^~~~~~~~~~~~~
towers.cpp:224:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |         if(r!=lt.size() and to[lt[r]]<se){
      |            ~^~~~~~~~~~~

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