Submission #1232128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232128		VMaksimoski008	Radio Towers (IOI22_towers)	C++20	23 / 100	4051 ms	12004 KiB

towers

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

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] );
}

int max_towers(int L, int R, int D) {
    int ans = 1;
    set<int> st;

    vector<pair<int, int> > ord;
    for(int i=L; i<=R; i++) ord.push_back({ a[i], i });
    sort(ord.begin(), ord.end());

    for(auto [h, id] : ord) {
        if(st.empty()) {
            st.insert(id);
            continue;
        }

        int ok = 1;
        auto it = st.lower_bound(id);

        if(it != st.end()) {
            if(*it == id + 1) {
                ok = 0;
            } else {
                int mx = query(id+1, *it-1); 
                if(max(a[id], a[*it]) > mx - D) ok = 0;
            }
        }

        if(it != st.begin()) {
            --it;
            if(*it == id - 1) {
                ok = 0;
            } else {
                int mx = query(*it+1, id-1);
                if(max(a[id], a[*it]) > mx - D) ok = 0;
            }
        }

        if(ok) {
            st.insert(id);
            ans++;
        }
    }

    return ans;
}

• 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