Submission #1137875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137875		onlk97	Radio Towers (IOI22_towers)	C++20	17 / 100	271 ms	9508 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
int n,a[100010],d[100010];
int sp[18][100010],Lg[100010];
int qry(int l,int r){
    if (l>r) return -1e9;
    int g=Lg[r-l+1];
    return max(sp[g][l],sp[g][r-(1<<g)+1]);
}
void init(int N,vector <int> H){
    n=N;
    for (int i=1; i<=n; i++) a[i]=H[i-1];
    for (int i=1; i<=n; i++) sp[0][i]=a[i];
    for (int j=1; (1<<j)<=n; j++){
        for (int i=1; i+(1<<j)-1<=n; i++) sp[j][i]=max(sp[j-1][i],sp[j-1][i+(1<<(j-1))]);
    }
    Lg[1]=0;
    for (int i=2; i<=n; i++) Lg[i]=Lg[i>>1]+1;
    int prv[n+1],nxt[n+1];
    stack <int> st;
    for (int i=1; i<=n; i++){
        while (!st.empty()&&a[st.top()]>a[i]) st.pop();
        if (st.empty()) prv[i]=0;
        else prv[i]=st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i=n; i; i--){
        while (!st.empty()&&a[st.top()]>a[i]) st.pop();
        if (st.empty()) nxt[i]=0;
        else nxt[i]=st.top();
        st.push(i);
    }
    for (int i=1; i<=n; i++){
        int lim=1e9;
        if (prv[i]) lim=min(lim,qry(prv[i]+1,i-1)-a[i]);
        if (nxt[i]) lim=min(lim,qry(i+1,nxt[i]-1)-a[i]);
        d[i]=lim;
    }
    sort(d+1,d+n+1);
}
int max_towers(int L,int R,int D){
    L++; R++;
    int idx=lower_bound(d+1,d+n+1,D)-d;
    return n+1-idx;
}

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