Submission #1074118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074118		shmax	Radio Towers (IOI22_towers)	C++17	27 / 100	690 ms	17608 KiB

towers

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

using namespace std;
#define bit(x, i) ((x >> i) & 1)

template<typename T>
using vec = vector<T>;
vec<int> h_;
int n_;
int peak;

void init(int N, std::vector<int> H) {
    h_ = H;
    n_ = N;
    peak = max_element(h_.begin(), h_.end()) - h_.begin();
}

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]);
    }
};

const int maxN = 1e5 + 10;
int stree[4 * maxN];

void init() {
    memset(stree, -1e9, sizeof stree);
}


void update(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) {
        stree[v] = val;
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm) update(2 * v, tl, tm, pos, val);
    else update(2 * v + 1, tm + 1, tr, pos, val);
    stree[v] = max(stree[2 * v], stree[2 * v + 1]);
}


int get(int v, int tl, int tr, int l, int r) {
    if (l > r) return -1e9;
    if (tl == l && tr == r) return stree[v];
    int tm = (tl + tr) / 2;
    return max(get(2 * v, tl, tm, l, min(r, tm)), get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}

int cnt = 0;


int max_towers1(int L, int R, int D) {


    if (L < peak and R > peak) {
        if (h_[peak] >= max(h_[L], h_[R]) + D) {
            return 2;
        }
        return 1;
    }
    return 1;
}


int max_towers2(int L, int R, int D) {
    vec<int> h;
    for (int i = L; i <= R; i++) h.push_back(h_[i]);
    int n = h.size();
    init();
    SparseTable stmax(h.begin(), h.end(), [](int a, int b) { return max(a, b); });
    vec<int> dp(n, 0);
    multiset<pair<int, int>> ms;

    for (int i = n - 1; i >= 0; i--) {
        dp[i] = 1;
        if (i == n - 1) {
            ms.insert({h[i], i});
            continue;
        }

        int tl = i + 1;
        int tr = n - 1;
        if (stmax.get(tl, tr) < h[i] + D) {
            while (!ms.empty()) {
                auto [val, idx] = *ms.begin();
                if (h[i] < val + D) break;
                ms.erase(ms.begin());
                update(1, 0, n - 1, idx, dp[idx]);
            }
            ms.insert({h[i], i});
        }
        while (tl != tr) {
            int tm = (tl + tr) / 2;
            if (stmax.get(i + 1, tm) >= h[i] + D) tr = tm;
            else tl = tm + 1;
        }
        dp[i] = max(dp[i], get(1, 0, n - 1, tl + 1, n - 1) + 1);
        while (!ms.empty()) {
            auto [val, idx] = *ms.begin();
            if (h[i] < val + D) break;
            ms.erase(ms.begin());
            update(1, 0, n - 1, idx, dp[idx]);
        }

        ms.insert({h[i], i});

//        int cur_max = h[i + 1];
//        for (int j = i + 2; j < n; j++) {
//            if (cur_max >= max(h[i], h[j]) + D) {
//                dp[i] = max(dp[i], dp[j] + 1);
//            }
//            cur_max = max(cur_max, h[j]);
//        }
    }

    return *max_element(dp.begin(), dp.end());
}


int max_towers(int L, int R, int D) {
    if (cnt > 1) {
        return max_towers1(L, R, D);
    } else {
        cnt++;
        return max_towers2(L, R, D);
    }
}

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:96:81:   required from here
towers.cpp:37: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]
   37 |         for (int i = 1; i < t.size(); i++)
      |                         ~~^~~~~~~~~~

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