Submission #682720

#	Time	Username	Problem	Language	Result	Execution time	Memory
682720		SirCovidThe19th	Radio Towers (IOI22_towers)	C++17	17 / 100	1228 ms	75828 KiB

towers

#include <bits/stdc++.h>
using namespace std; 

const int mx = 1e5 + 5;

struct pstNode{
    int sum, mn, mx;
};
struct segNode{
    int mn, mx, dif1, dif2;
};

pstNode comb(pstNode a, pstNode b){
    return {a.sum + b.sum, min(a.mn, b.mn), max(a.mx, b.mx)};
};
segNode comb(segNode a, segNode b){
    return {min(a.mn, b.mn), max(a.mx, b.mx), max({a.dif1, b.dif1, b.mx - a.mn}), max({a.dif2, b.dif2, a.mx - b.mn})};
}

struct persistentSegTree{
    pstNode seg[mx * 31]; int idx = 1, lc[mx * 31] = {}, rc[mx * 31] = {};

    persistentSegTree(){ 
        fill(seg, seg + mx * 31, pstNode({0, int(1e9), 0})); 
    }
    void dup(int &i){
        lc[idx] = lc[i];
        rc[idx] = rc[i];
        seg[idx] = seg[i];
        i = idx; idx++;
    }
    void upd(int p, int &i, int l = 0, int r = mx){
        dup(i);
        if (l == r){ seg[i] = {1, l, l}; return; }

        int mid = (l + r) / 2;
        if (p <= mid) upd(p, lc[i], l, mid);
        else upd(p, rc[i], mid + 1, r);

        seg[i] = comb(seg[lc[i]], seg[rc[i]]);
    }
    pstNode qry(int ql, int qr, int i, int l = 0, int r = mx){
        if (qr < l or ql > r or !i) return {0, int(1e9), 0};
        if (l >= ql and r <= qr) return seg[i];
        int mid = (l + r) / 2;
        return comb(qry(ql, qr, lc[i], l, mid), qry(ql, qr, rc[i], mid + 1, r));
    }
};
struct segTree{
    segNode seg[mx * 2 + 5];

    void upd(int i, int val){
        seg[i += mx] = {val, val, 0, 0};
        for (i /= 2; i > 0; i /= 2) seg[i] = comb(seg[i * 2], seg[i * 2 + 1]);
    }
    segNode qry(int l, int r){ 
        segNode retL = segNode({int(1e9), 0, 0, 0});
        segNode retR = segNode({int(1e9), 0, 0, 0});

        for (l += mx, r += mx; l <= r; r /= 2, l /= 2){
            if (l % 2 == 1) retL = comb(retL, seg[l++]);
            if (r % 2 == 0) retR = comb(seg[r--], retR);
        }
        return comb(retL, retR);
    }
};
struct sparseTable{
    int rmq[mx][17];

    void build(vector<int> A){
        for (int j = 0; j < 17; j++)
            for (int i = 0; i + (1 << j) - 1 < A.size(); i++)
                rmq[i][j] = !j ? A[i] : max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
    }
    int qry(int l, int r){
        int lg = 31 - __builtin_clz(r - l + 1);
        return max(rmq[l][lg], rmq[r - (1 << lg) + 1][lg]);
    }
};

vector<int> H; map<int, int> root; segTree st; persistentSegTree pst; sparseTable fastMax;

int max_towers(int l, int r, int d){
    auto it = root.lower_bound(d);
    pstNode ret = pst.qry(l, r, it->second);
    
    if (ret.sum == 0){
        int maxDif = max(st.qry(l, r).dif1, st.qry(l, r).dif2);
        return maxDif >= d ? 2 : 1;
    }
    
    int lo = l, hi = ret.mn;
    while (lo < hi){
        int mid = (lo + hi + 1) / 2;
        (fastMax.qry(mid, ret.mn) >= H[ret.mn] + d ? lo = mid : hi = mid - 1); 
    }
    ret.sum += (H[lo] >= H[ret.mn] + d and st.qry(l, lo).dif1 >= d);

    lo = ret.mx, hi = r;
    while (lo < hi){
        int mid = (lo + hi) / 2;
        (fastMax.qry(ret.mx, mid) >= H[ret.mx] + d ? hi = mid : lo = mid + 1);
    }
    ret.sum += (H[hi] >= H[ret.mx] + d and st.qry(hi, r).dif2 >= d);
    return ret.sum;
}
void init(int n, vector<int> h_){
    H = h_;
    fastMax.build(H);

    int L[n], R[n]; 
    for (int i = 0; i < n; i++) L[i] = R[i] = -1;
    
    stack<int> stk;
    for (int i = 0; i < n; i++){
        st.upd(i, H[i]);
        while (stk.size() and H[stk.top()] >= H[i]){
            R[stk.top()] = i;
            stk.pop();
        }
        if (stk.size()) L[i] = stk.top();
        stk.push(i);
    }

    vector<pair<int, int>> V;
    for (int i = 0; i < n; i++){
        int dlim = 1e9;
        if (L[i] != -1) dlim = min(dlim, fastMax.qry(L[i], i) - H[i]);
        if (R[i] != -1) dlim = min(dlim, fastMax.qry(i, R[i]) - H[i]);
        V.push_back({dlim, i});
    }
    sort(V.begin(), V.end(), greater<pair<int, int>>());

    int curRoot = 1;
    for (auto [dlim, i] : V){
        pst.upd(i, curRoot);
        root[dlim] = curRoot;
    }
}

Compilation message (stderr)

towers.cpp: In member function 'void sparseTable::build(std::vector<int>)':
towers.cpp:72:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for (int i = 0; i + (1 << j) - 1 < A.size(); i++)
      |                             ~~~~~~~~~~~~~~~~~^~~~~~~~~~

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