Submission #914867

#	Time	Username	Problem	Language	Result	Execution time	Memory
914867		bobbilyking	Radio Towers (IOI22_towers)	C++17	100 / 100	812 ms	56000 KiB

towers

/*

step 1. we really only care about peaks and valleys of the array
step 2. once we have the list of peaks, precompute the valleys to the left and right of each peak. The "glue value" of the peak is Height[peak] - max(Height[left valley], Height[right valley]), which the maximum D value allowed s.t. this peak can be the transmission tower between the two adjacent valleys

Step 3. Put these peaks in a 2d segtree, represetning (position, value, original index in array). This segtree needs to be able to support:

    // Queries in the range [l, r] for all res values (peaks with glue value) >= D, and then returns 
    // how many items were in the range, the minimum indexed peak, and maximum indexed peak of said range.

Step 4. The answer is simply doing the above query, this gets us the # of peaks, then do some fixing on the endpoints to make sure that the left and right endpoints are valid valleys or not.

Proof of why this works:

Intuitively, what the final construction is doing is using the peaks as "glue" values for the valleys and then verifying that all gaps work. 

The construction works as a lower bound, since by definition of how we put things into the segtree, the valleys on both sides are valid to select (except as an endpoint). Even if we skip peaks, if two peaks satisfy the >=D property, one of the valleys on both sides must satisfy it. 

(WLOG, Let's say H[peak_l] < H[peak_r], and both are selected. This means that H[right_valley[peak_l]] is a valid transition point).

So all glue points work, we can select a valley between any of them. We just need to take care about the valleys on the endpoints, but that is an easy fix. 

To show this is an upper bound: (SKETCH)

First recall that only peaks are useful as "glue" and valleys are useful as chosen towers (except at endpoints which we handle already).

With our segtree query, we only ever query peaks in the range with a sufficiently high glue value, so we need to show that having one of these peaks without a sufficiently high glue value will never work.

Well, that's easy: "insufficient glue value" means that we can't pick both of the adjacent valleys in our answer; we can only pick one of them. But if we can only pick one of them, then there's no point in using this peak as a glue value. So our query is correct in not picking this peak as a glue value.

What about the endpoints: Notice that the endpoints can only make not-valleys seem like valleys, i.e. shrink the effective D value, so we're only ever selecting a potentially incorrect glue value, and fixing it afterwards; we never miss a candidate solution. 

====================================================================================================================

	[ a bit confusing argument down below] 

	- Formally, you'd first make the claim that glue towers must be peaks; this can be shown fairly easily. Then, you use an exchange argument: The two valleys adjacent to a useless peak can't be selected, so we must select only one of them. Like this
	
	Originally, we have
	
	P V (useless peak) V P 
	
	First, (useless peak) cannot join the two V's by definition. So we can't select both V's. So we only select one of them. WLOG select the left V.
	
	P V | (useless peak) _ P
	
	If we selected P as glue in our query, that means height(P) > height(useless peak), since the useless valley contributed to both of their precomps.  
	
	If we didn't, you can probably propogate the value until we actually select a glue P and gg.

The "fixing" side is hard to express here but it should be clear in the code
*/

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define F(i, l, r) for (ll i = ll(l); i < ll(r); ++i)
#define FD(i, l, r) for (ll i = ll(l); i > ll(r); --i)
#define A(a) (a).begin(), (a).end()
#define K first
#define V second

template<typename T> struct SparseTable {
    int n,log2=0;
    function<T(T, T)> merge;
    T id ;
    vector<vector<T>> a = {{}};
    SparseTable(const vector<T>& v, function<T(T, T)> _merge, T _id): merge(_merge), id(_id) {
        n = v.size();
        while((1<<log2) <= n) {
            ++log2;
        }
        a.resize(log2);
        a[0] = v;
        for(int i=1,len=1;i<log2;++i,len*=2) {
            a[i].resize(n + 1 - (1<<i));
            for(size_t j=0;j<a[i].size();++j) {
                a[i][j] = merge(a[i-1][j], a[i-1][j + len]);
            }
        }
    }
    SparseTable(){}
    T query(int l, int r) { // [l,r)
        if (r <= l) return id;
        int len = __lg(r-l);
        return merge(a[len][l], a[len][r- (1<<len)]);
    }   
};

SparseTable<ll> spmin;
 

const int MAXN = 100010, INF = 1000000010;

namespace seg {
    pl merge(pl a, pl b) {
        return pair(min(a.K, b.K), max(a.V, b.V));
    }

    struct node{    
        vector<pl> vec;
        vector<pl> indices; // {mn, mx}
        node(){};
        node(int value, int pos){
            vec.emplace_back(value, pos);
            indices.emplace_back(pos, pos);
        }
        node(node& a, node& b){
            vec.resize(a.vec.size() + b.vec.size());
            indices.resize(vec.size());
            merge(a.vec.begin(), a.vec.end(), b.vec.begin(), b.vec.end(), vec.begin());
            pl cur(MAXN, -1);

            // All items are now in sorted order, relative to first key.
            // mn and max represent the range of indices 
            FD(i, ll(vec.size())-1, -1) indices[i] = cur = merge(pair(vec[i].V, vec[i].V), cur);
        }
    };

    node tr[2*MAXN];

    pair<int, pl> query(int l, int r, int x){
        int cnt=0;
        pl res(MAXN, -1);

        auto handle = [&](node& cur) {
            auto &[vec, indices] = cur;
            auto itr = lower_bound(A(vec), pair(x, -1));
            int pos = (int)(itr - vec.begin());
            cnt += (int)(vec.end() - itr);
            if(itr!=vec.end()) res = merge(res, indices[pos]);
        };

        for(l+=MAXN, r+=MAXN; l<r; l>>=1, r>>=1){
            if(l&1) handle(tr[l++]);
            if(r&1) handle(tr[--r]);
        }

        return {cnt, res};
    }

    void build(vl res) {
        F(i, 0, res.size()) seg::tr[MAXN+i]=seg::node(res[i], i);
        FD(i, MAXN-1, -1) tr[i]=node(tr[i<<1], tr[i<<1|1]);
    }
}
 
 
int arr[MAXN];
 
void init(int n, vector<int> H) {
    vl maxl(n), maxr(n);
    copy(A(H), arr);

    spmin = SparseTable<ll>(H, [](ll a, ll b) {
        return min(a, b);
    }, INF);

    F(i, 0, n) {
        int x;
        for(x=i-1; x!=-1 && H[x]<H[i]; x=maxl[x]);
        maxl[i]=x;
    }

    FD(i, n-1, -1) {
        int x;
        for(x=i+1; x!=n && H[x]<H[i]; x=maxr[x]);
        maxr[i]=x;
    }
    // maxl and maxr finds closest node greater than it to left and right ? not sure 

    vl res(n);

    F(i, 0, n) {
        int l = maxl[i], r = maxr[i];
        // H[i] is trying to glue the left and right, so it must take the max of 
        // the two valleys to either side.
        res[i] = H[i] - max(spmin.query(l+1, i), spmin.query(i+1, r));
    }

    seg::build(res);
}
 
int max_towers(int L, int R, int D) {
    // Queries in the range [l, r] for all res values (peaks with glue value) >= D, and then returns 
    // how many items were in the range, the minimum indexed peak, and maximum indexed peak of said range.
    auto [cnt, indices] = seg::query(L, R+1, D);
    if(!cnt) return 1;
    auto [mn, mx] = indices;

    // we want to find something to lease to the left and right
    // since we're only counting peaks (we actually lease valleys)
    // we would like to lease (cnt+1) things since (cnt+1) gaps,
    // but need to make sure endpoints are legit

    bool sa = (D > arr[mn] - spmin.query(L, mn));
    bool sb = (D > arr[mx] - spmin.query(mx+1, R+1));

    return max(1, (cnt + 1) - sa - sb);
}

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