oj.uz

Submission #776912

# Submission time Handle Problem Language Result Execution time Memory
776912 2023-07-08T11:42:48 Z alexander707070 Radio Towers (IOI22_towers) C++17
0 / 100
 638 ms 5172 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 485 ms 2788 KB 2nd lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '16'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '16'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 638 ms 5172 KB 1st lines differ - on the 1st token, expected: '11903', found: '11813'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 201 ms 1616 KB 1st lines differ - on the 1st token, expected: '7197', found: '7969'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '16'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 485 ms 2788 KB 2nd lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -