Submission #1074458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074458		shmax	Radio Towers (IOI22_towers)	C++17	17 / 100	761 ms	43864 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>

using namespace std;
#define bit(x, i) ((x >> i) & 1)
#define inf 2000'000'000LL
template<typename T>
using vec = vector<T>;


template<typename it>
struct SparseTable {

    using T = typename remove_reference<decltype(*declval<it>())>::type;
    vector<vector<T>> t;
    function<T(T, T)> f;
    vector<int> log;

    SparseTable() = default;

    SparseTable(it first, it last, function<T(T, T)> op) : t(1), f(op) {
        int n = distance(first, last);
        t.assign(32 - __builtin_clz(n), vector<T>(n));
        t[0].assign(first, last);
        log.resize(n + 1);
        for (int i = 2; i <= n; i++)
            log[i] = log[i / 2] + 1;

        for (int i = 1; i < t.size(); i++)
            for (int j = 0; j < n - (1 << i) + 1; j++)
                t[i][j] = f(t[i - 1][j], t[i - 1][j + (1 << (i - 1))]);
    }

    T get(int l, int r) {
        int h = log[r - l + 1];
        return f(t[h][l], t[h][r - (1 << h) + 1]);
    }
};

struct node {
    int l, r;
    int sum;
};
vec<node> nodes;

void fetch(int x) {
    int sm = 0;
    if (nodes[x].l != -1) {
        sm += nodes[nodes[x].l].sum;
    }
    if (nodes[x].r != -1) {
        sm += nodes[nodes[x].r].sum;
    }
    nodes[x].sum = sm;
}

int new_node() {
    nodes.push_back({-1, -1, 0});
    return nodes.size() - 1;
}

vec<int> roots;

int build(int tl, int tr) {
    if (tl == tr) {
        int id = new_node();
        nodes[id].sum = 0;
        return id;
    }
    int id = new_node();
    int tm = (tl + tr) / 2;
    int l = build(tl, tm);
    int r = build(tm + 1, tr);
    nodes[id].l = l;
    nodes[id].r = r;
    fetch(id);
    return id;
}

int get(int v, int tl, int tr, int l, int r) {
    if (tl == l and tr == r) {
        return nodes[v].sum;
    }
    int tm = (tl + tr) / 2;
    if (r <= tm) {
        return get(nodes[v].l, tl, tm, l, r);
    }
    if (l > tm) {
        return get(nodes[v].r, tm + 1, tr, l, r);
    }
    return get(nodes[v].l, tl, tm, l, tm) + get(nodes[v].r, tm + 1, tr, tm + 1, r);
}

int update(int v, int tl, int tr, int pos, int x) {
    if (tl == tr) {
        int id = new_node();
        nodes[id].sum = x;
        return id;
    }
    int tm = (tl + tr) / 2;
    int id = new_node();
    if (pos <= tm) {
        int tid = update(nodes[v].l, tl, tm, pos, x);
        nodes[id].l = tid;
        nodes[id].r = nodes[v].r;
    } else {
        int tid = update(nodes[v].r, tm + 1, tr, pos, x);
        nodes[id].l = nodes[v].l;
        nodes[id].r = tid;
    }
    fetch(id);
    return id;
}

vec<int> h;
int n;
vec<pair<int, int>> deltas;

void init(int N, std::vector<int> H) {
    n = N;
    h = H;
    SparseTable stmin(h.begin(), h.end(), [](int a, int b) { return min(a, b); });
    SparseTable stmax(h.begin(), h.end(), [](int a, int b) { return max(a, b); });
    for (int i = 0; i < n; i++) {
        int h1 = inf;
        if (i != 0) {
            if (stmin.get(0, i - 1) < h[i]) {
                int tl = 0;
                int tr = i - 1;
                while (tl != tr) {
                    int tm = (tl + tr + 1) / 2;
                    if (stmin.get(tm, i - 1) < h[i]) {
                        tl = tm;
                    } else {
                        tr = tm - 1;
                    }
                }
                h1 = stmax.get(tl, i - 1);
            }
        }
        int h2 = inf;
        if (i != n - 1) {
            if (stmin.get(i + 1, n - 1) < h[i]) {
                int tl = i + 1;
                int tr = n - 1;
                while (tl != tr) {
                    int tm = (tl + tr) / 2;
                    if (stmin.get(i + 1, tm) < h[i]) {
                        tr = tm;
                    } else {
                        tl = tm + 1;
                    }
                }
                h2 = stmax.get(i + 1, tr);
            }
        }
        int max_delta = min(h1, h2) - h[i];
        deltas.push_back({max_delta, i});
    }

    sort(deltas.rbegin(), deltas.rend());
    int t = build(0, n - 1);
    roots.push_back(t);
    for (auto [d, i]: deltas) {
        t = update(roots.back(), 0, n - 1, i, 1);
        roots.push_back(t);
    }
}

int max_towers(int L, int R, int D) {
    int tl = 0;
    int tr = n - 1;
    while (tl != tr) {
        int tm = (tl + tr + 1) / 2;
        if (deltas[tm].first >= D) {
            tl = tm;
        } else {
            tr = tm - 1;
        }
    }
    if (deltas[0].first < D)
        tl = -1;
    int vr = roots[tl + 1];
    int ans = get(vr, 0, n - 1, L, R);
    return ans;
}

Compilation message (stderr)

towers.cpp: In instantiation of 'SparseTable<it>::SparseTable(it, it, std::function<typename std::remove_reference<decltype (* declval<it>())>::type(typename std::remove_reference<decltype (* declval<it>())>::type, typename std::remove_reference<decltype (* declval<it>())>::type)>) [with it = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; typename std::remove_reference<decltype (* declval<it>())>::type = int]':
towers.cpp:122:81:   required from here
towers.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int>, std::allocator<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int i = 1; i < t.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