Submission #1164873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164873		SmuggingSpun	Radio Towers (IOI22_towers)	C++20	0 / 100	662 ms	54472 KiB

towers

#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 1e5 + 5;
const int INF = 2e9;
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 n, l_min[lim], r_min[lim], h[lim], log_v[lim], st_dif[lim << 2], spt_max[lim][17], spt_min[lim][17];
vector<Node>st;
vector<pair<int, int>>a(1, make_pair(INF, -1));
int get_min(int l, int r){
    int k = log_v[r - l + 1];
    return min(spt_min[l][k], spt_min[r - (1 << k) + 1][k]);
}
int get_max(int l, int r){
    int k = log_v[r - l + 1];
    return max(spt_max[l][k], spt_max[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 build_dif(int id = 1, int l = 1, int r = n){
    if(l == r){
        st_dif[id] = 0;
        return;
    }
    int m = (l + r) >> 1;
    build(id << 1, l, m);
    build(id << 1 | 1, m + 1, r);
    st_dif[id] = max({st_dif[id << 1], st_dif[id << 1 | 1], get_max(m + 1, r) - get_min(l, m)});
}
int get_dif(int u, int v, int id = 1, int l = 1, int r = n){
    if(l > v || r < u){
        return 0;
    }   
    if(u <= l && v >= r){
        return st_dif[id];
    }
    int m = (l + r) >> 1;
    if(m >= v){
        return get_dif(u, v, id << 1, l, m);
    }
    if(m < u){
        return get_dif(u, v, id << 1 | 1, m + 1, r);
    }
    return max({get_dif(u, v, id << 1, l, m), get_dif(u, v, id << 1 | 1, m + 1, r), get_max(m + 1, v) - get_min(u, m)});
}
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_max[i + 1][0] = spt_min[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_min[i][j] = min(spt_min[i][j - 1], spt_min[i + (1 << (j - 1))][j - 1]);
            spt_max[i][j] = max(spt_max[i][j - 1], spt_max[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(l_min[i] == 0 ? INF : get_max(l_min[i] + 1, i), r_min[i] == n + 1 ? INF : get_max(i, r_min[i] - 1)) - h[i], i);
    }
    sort(a.begin(), a.end(), greater<pair<int, int>>());
    st.assign(n + 1, Node());
    build();
    build_dif();
    for(int i = 1; i <= n; i++){
        st[i] = st[i - 1];
        update(i, a[i].second);
    }
}
int get(int id, int u, int v, int l = 1, int r = n){
    if(l > v || r < u){
        return 0;
    }
    if(u <= l && v >= r){
        return st[id].cnt;
    }
    int m = (l + r) >> 1;
    return get(st[id].l, u, v, l, m) + get(st[id].r, u, v, m + 1, r);
}
int max_towers(int l, int r, int d){
    int low = 1, high = n, id = 0;
    while(low <= high){
        int mid = (low + high) >> 1;
        if(a[mid].first >= d){
            low = (id = mid) + 1;
        }
        else{
            high = mid - 1;
        }
    }
    if(get(id, ++l, ++r) < 2){
        return 1;
    }
    low = l;
    high = r;
    int L, R;
    while(low <= high){
        int mid = (low + high) >> 1;
        if(get(id, l, mid) > 0){
            high = (L = mid) - 1; 
        } 
        else{
            low = mid + 1;
        }
    }
    low = l;
    high = r;
    while(low <= high){
        int mid = (low + high) >> 1;
        if(get(id, mid, r) > 0){
            low = (R = mid) + 1;
        }
        else{
            high = mid - 1;
        }
    }
    int pl = 0, pr = n + (low = 1);
    high = L;
    while(low <= high){
        int mid = (low + high) >> 1;
        if(get_max(mid, L) - d >= h[L]){
            low = (pl = mid) + 1;
        }
        else{
            high = mid - 1;
        }
    }
    low = R;
    high = n;
    while(low <= high){
        int mid = (low + high) >> 1;
        if(get_max(R, mid) - d >= h[R]){
            high = (pr = mid) - 1;
        }
        else{
            low = mid + 1;
        }
    }
    return get(id, l, r) + int(get_dif(l, pl) >= d) + int(get_dif(pr, r) >= d);
}

• 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