Submission #1164806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164806		SmuggingSpun	Radio Towers (IOI22_towers)	C++20	Compilation error	0 ms	0 KiB

towers

#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 1e5 + 5;
template<class T>void maximize(T& a, T b){
    if(a < b){
        a = b;
    }
}
struct Node{
    int cnt, l, r;
    Node(){
        this->cnt = 0;
        this->l = this->r = -1;
    }
};
int l_min[lim], r_min[lim], h[lim], log_v[lim], spt[lim][17];
vector<Node>st;
vector<pair<int, int>>a(1, make_pair(-1, -1));
int get_max(int l, int r){
    int k = log_v[r - l + 1];
    return max(spt[l][k], spt[r - (1 << k) + 1][k]);
}
void update(int id, int p){
    int l = 1, r = n;
    while(l < r){
        st[id].cnt++;
        int m = (l + r) >> 1;
        if(m < p){
            st.emplace_back(st[st[id].r]);
            st[id].r = int(st.size()) - 1;
            id = st[id].r;
            l = m + 1;
        }
        else{
            st.emplace_back(st[st[id].l]);
            st[id].l = int(st.size()) - 1;
            id = st[id].l;
            r = m;
        }
    }
    st[id].cnt++;
}
void build(int id = 0, int l = 1, int r = n){
    if(l == r){
        return;
    }
    st[id].l = st.size();
    st.emplace_back(Node());
    st[id].r = st.size();
    st.emplace_back(Node());
    int m = (l + r) >> 1;
    build(st[id].l, l, m);
    build(st[id].r, m + 1, r);
}
void init(int N, vector<int>H){
    log_v[0] = -1;
    for(int i = 1; i < lim; i++){
        log_v[i] = log_v[i >> 1] + 1;
    }
    n = N;
    for(int i = 0; i < n; i++){
        spt[i + 1][0] = h[i + 1] = H[i];
    }
    for(int j = 1; j < 17; j++){
        for(int i = 1; i + (1 << j) - 1 <= n; i++){
            spt[i][j] = max(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
        }
    }
    stack<int>stk;
    for(int i = 1; i <= n; stk.push(i++)){
        while(!stk.empty() && h[i] > h[stk.top()]){
            stk.pop();
        }
        l_min[i] = (stk.empty() ? 0 : stk.top());
    }
    while(!stk.empty()){
        stk.pop();
    }
    for(int i = n; i > 0; stk.push(i--)){
        while(!stk.empty() && h[i] > h[stk.top()]){
            stk.pop();
        }
        r_min[i] = (stk.empty() ? n + 1 : stk.top());
    }
    for(int i = 1; i <= n; i++){
        a.emplace_back(min(get_max(l_min[i] + 1, i), get_max(i, r_max[i] - 1)) - h[i], i);
    }
    sort(a.begin(), a.end());
    st.assign(n + 1, Node());
    build();
    for(int i = 0; i < n; i++){
        st[i + 1] = st[i];
        update(i + 1, i);
    }
}
int max_towers(int l, int r, int d){
    return st[upper_bound(a.begin(), a.end(), make_pair(d, -1)) - a.begin() - 1].cnt;
}

Compilation message (stderr)

towers.cpp: In function 'void update(int, int)':
towers.cpp:25:20: error: 'n' was not declared in this scope
   25 |     int l = 1, r = n;
      |                    ^
towers.cpp: At global scope:
towers.cpp:44:43: error: 'n' was not declared in this scope
   44 | void build(int id = 0, int l = 1, int r = n){
      |                                           ^
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:61:5: error: 'n' was not declared in this scope
   61 |     n = N;
      |     ^
towers.cpp:87:65: error: 'r_max' was not declared in this scope
   87 |         a.emplace_back(min(get_max(l_min[i] + 1, i), get_max(i, r_max[i] - 1)) - h[i], i);
      |                                                                 ^~~~~