Submission #1232153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232153		VMaksimoski008	Radio Towers (IOI22_towers)	C++20	0 / 100	215 ms	10732 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e5 + 5;

vector<int> V;
int a[mxn], n, T[mxn][20];

int query(int l, int r) {
    int k = __lg(r - l + 1);
    return max( T[l][k], T[r-(1<<k)+1][k] );
}

void init(int _n, vector<int> H) {
    n = _n;
    for(int i=0; i<n; i++) {
        a[i] = H[i];
        T[i][0] = a[i];
    }

    for(int j=1; j<20; j++)
        for(int i=0; i+(1<<j)-1<n; i++)
            T[i][j] = max( T[i][j-1], T[i+(1<<(j-1))][j-1] );

    vector<int> L(n, -1), R(n, n);

    stack<int> st;
    for(int i=0; i<n; i++) {
        while(!st.empty() && a[st.top()] >= a[i]) st.pop();
        if(!st.empty()) L[i] = st.top();
        st.push(i);
    }

    while(!st.empty()) st.pop();

    for(int i=n-1; i>=0; i--) {
        while(!st.empty() && a[st.top()] >= a[i]) st.pop();
        if(!st.empty()) R[i] = st.top();
        st.push(i);
    }

    for(int i=0; i<n; i++) {
        if(L[i] == i-1 && R[i] == i+1) {
            V.push_back(-1e9);
            continue;
        }

        int mx = 1e9;
        if(L[i] != i-1) mx = min(mx, query(L[i]+1, i-1));
        if(R[i] != i+1) mx = min(mx, query(i+1, R[i]-1));
        V.push_back(mx);
    }
    sort(V.begin(), V.end());
}

int max_towers(int L, int R, int D) {
    int l=0, r=n-1, p=n-1;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(V[mid] >= D) p = mid, r = mid - 1;
        else l = mid + 1;
    }

    return n-p;
}

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