제출 #914860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914860		vjudge1	Radio Towers (IOI22_towers)	C++17	100 / 100	895 ms	56272 KiB

towers

#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