oj.uz

Submission #776942

# Submission time Handle Problem Language Result Execution time Memory
776942 2023-07-08T12:11:04 Z alexander707070 Radio Towers (IOI22_towers) C++17
4 / 100
 739 ms 2512 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,k;
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];
    }
    for(int i=1;i<=n;i++){
        if(h[i]>h[i-1] and h[i]>h[i+1])k=i;
    }
    buildmax(1,1,n);
}

int max_towers(int L, int R, int D){
    L++; R++;
    if(R<=k or L>=k)return 1;

    if(max(h[L],h[R])<=h[k]-D)return 2;
    return 1;
}

/*
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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 1488 KB Output is correct
2 Correct 574 ms 2512 KB Output is correct
3 Correct 739 ms 2472 KB Output is correct
4 Correct 601 ms 2512 KB Output is correct
5 Correct 627 ms 2376 KB Output is correct
6 Correct 615 ms 2512 KB Output is correct
7 Correct 589 ms 2476 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 1488 KB Output is correct
2 Correct 574 ms 2512 KB Output is correct
3 Correct 739 ms 2472 KB Output is correct
4 Correct 601 ms 2512 KB Output is correct
5 Correct 627 ms 2376 KB Output is correct
6 Correct 615 ms 2512 KB Output is correct
7 Correct 589 ms 2476 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '1'
12 Halted 0 ms 0 KB -