Submission #896852

#	Time	Username	Problem	Language	Result	Execution time	Memory
896852		abcvuitunggio	Radio Towers (IOI22_towers)	C++17	23 / 100	4083 ms	3160 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=2e9;
int l[100001],r[100001],a[100001],b[100001];
stack <int> st;
void init(int N, vector <int> H){
    for (int i=0;i<N;i++){
        a[i]=b[i]=H[i];
        r[i]=N-1;
        while (!st.empty()&&H[st.top()]>H[i]){
            r[st.top()]=i-1;
            a[i]=max(a[i],a[st.top()]);
            int x=b[st.top()];
            st.pop();
            if (!st.empty())
                b[st.top()]=max(b[st.top()],x);
        }
        l[i]=(st.empty()?0:st.top()+1);
        st.push(i);
    }
    for (int i=0;i<N;i++){
        a[i]-=H[i];
        b[i]-=H[i];
        if (!l[i])
            a[i]=INF;
        if (r[i]==N-1)
            b[i]=INF;
        l[i]--;
        r[i]++;
    }
}
int max_towers(int L, int R, int D){
    int res=0;
    for (int i=L;i<=R;i++){
        int x=INF,y=INF;
        if (l[i]>=L)
            x=a[i];
        if (r[i]<=R)
            y=b[i];
        res+=(min(x,y)>=D);
    }
    return res;
}

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