oj.uz

답안 #787115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
787115 2023-07-18T20:34:09 Z alexander707070 송신탑 (IOI22_towers) C++17
0 / 100
 4000 ms 7116 KB 
#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
 
int n,h[MAXN],maxh,num,delta,from[MAXN],to[MAXN],border;
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,1,n,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,1,n,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 init(int N,vector<int> H){
    n=N;
    for(int i=1;i<=n;i++){
        h[i]=H[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){
    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]]<=R){
            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]]>=border)ans++;

        if(ans==0)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";
}
*/

Compilation message

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:155:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         if(se==poss.size())se=R+1;
      |            ~~^~~~~~~~~~~~~
towers.cpp:172:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |         if(r!=lt.size() and to[lt[r]]<=R){
      |            ~^~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4024 ms 7116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '15'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '15'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 729 ms 5808 KB 1st lines differ - on the 1st token, expected: '11903', found: '11904'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4019 ms 1616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '15'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4024 ms 7116 KB Time limit exceeded
2 Halted 0 ms 0 KB -