제출 #776912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776912		alexander707070	송신탑 (IOI22_towers)	C++17	0 / 100	638 ms	5172 KiB

towers

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

struct node{
    int lt,rt;
    int ans;
};

int n,h[MAXN],maxh,num,d;
int dp[MAXN],ans;

int maxs[4*MAXN];
node tree[4*MAXN];
bool ok;

void buildmax(int v,int l,int r){
    if(l==r){
        maxs[v]=h[l];
    }else{
        int tt=(l+r)/2;
        buildmax(2*v,l,tt);
        buildmax(2*v+1,tt+1,r);
        maxs[v]=max(maxs[2*v],maxs[2*v+1]);
    }
}

int getmax(int v,int l,int r,int ll,int rr){
    if(ll>rr)return -1;
    if(l==ll and r==rr){
        return maxs[v];
    }else{
        int tt=(l+r)/2;
        return max( getmax(2*v,l,tt,ll,min(tt,rr)) , getmax(2*v+1,tt+1,r,max(tt+1,ll),rr) );
    }
}

node combine(node fr,node sc){
    if(fr.ans==-1)return sc;
    if(sc.ans==-1)return fr;

    if(getmax(1,1,n,fr.rt+1,sc.lt-1)-d>=max(h[fr.rt],h[sc.lt])){
        return {fr.lt,sc.rt,fr.ans+sc.ans};
    }else{
        if(sc.ans==1 and fr.ans==1){
            if(h[fr.lt]<h[sc.lt]){
                return {fr.lt,fr.lt,1};
            }else{
                return {sc.lt,sc.lt,1};
            }
        }else if(sc.ans==1){
            return {fr.lt,sc.rt,fr.ans+sc.ans-1};
        }else if(fr.ans==1){
            return {sc.lt,sc.rt,fr.ans+sc.ans-1};
        }else{
            return {fr.lt,sc.rt,fr.ans+sc.ans-1};
        }
    }
}

void build(int v,int l,int r){
    if(l==r){
        tree[v]={l,l,1};
    }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]);
    }
}

node getinfo(int v,int l,int r,int ll,int rr){
    if(ll>rr)return {-1,-1,-1};
    if(l==ll and r==rr){
        return tree[v];
    }else{
        int tt=(l+r)/2;
        return combine( getinfo(2*v,l,tt,ll,min(tt,rr)) , getinfo(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];
    }
    buildmax(1,1,n);
}

int max_towers(int L, int R, int D){
    if(!ok){
        build(1,1,n); ok=true;
    }
    L++; R++;
    return getinfo(1,1,n,L,R).ans;
}

/*
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: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23