Submission #787092

#	Time	Username	Problem	Language	Result	Execution time	Memory
787092		alexander707070	Radio Towers (IOI22_towers)	C++17	23 / 100	4026 ms	12376 KiB

towers

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
 
int n,h[MAXN],maxh,num;
int dp[MAXN],ans,pref[MAXN];
 
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) );
    }
}
 
void init(int N,vector<int> H){
    n=N;
    for(int i=1;i<=n;i++){
        h[i]=H[i-1];
    }

    for(int i=1;i<=n;i++){
        if(h[i]<h[i-1] and h[i]<h[i+1])pref[i]++;
        pref[i]+=pref[i-1];
    }

    build(1,1,n);
}
 
int solve(int l,int r,int maxh,int d){
    if(l>r)return 0;
 
    int pos=best(1,1,n,l,r).second;
 
    int z=0;
    if(minh(1,1,n,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){
    L++; R++;
    if(D==1){
        ans=0;
        if(L<R)ans=pref[R-1]-pref[L];
        if(L!=R and h[L]<h[L+1])ans++;
        if(L!=R and h[R]<h[R-1])ans++;
        return ans;   
    }

    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";
}
*/

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