Submission #968983

#	Time	Username	Problem	Language	Result	Execution time	Memory
968983		maksim1744	Radio Towers (IOI22_towers)	C++17	100 / 100	1095 ms	111400 KiB

towers

/*
    author:  Maksim1744
    created: 24.04.2024 03:13:57
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#define OSTREAM(...)    ;
#define OSTREAM0(...)   ;
#endif

template<typename T, typename F = std::function<T(const T&, const T&)>>
struct SparseTable {
    vector<vector<T>> table;
    vector<int> p2;
    F combine;

    SparseTable(int n, F combine) : combine(combine) {
        while ((1 << table.size()) <= n || table.empty())
            table.emplace_back(n);
    }
    template<typename U>
    SparseTable(const vector<U>& v, F combine) : SparseTable<T>(v.size(), combine) {
        table[0].assign(v.begin(), v.end());
        build();
    }

    void build() {
        p2.resize(table[0].size() + 1);
        for (int i = 2; i < p2.size(); ++i)
            p2[i] = p2[i / 2] + 1;
        for (int i = 1; i < table.size(); ++i) {
            for (int j = 0; j + (1 << i) <= table[i].size(); ++j) {
                table[i][j] = combine(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    T ask(int l, int r) {
        int ln = p2[r - l + 1];
        if (r - l + 1 == ln) return table[ln][l];
        return combine(table[ln][l], table[ln][r - (1 << ln) + 1]);
    }
};

const int inf = 2e9;

int n;
vector<int> h;
SparseTable<int> sparse_min(1, [](int a, int b) { return min(a, b); });
SparseTable<int> sparse_max(1, [](int a, int b) { return max(a, b); });
vector<int> hill, valley;

struct Data {
    int len = 0;
    int left = -1;
    int last_new = -1;

    Data() {}
    Data(int x, int ind) {
        left = x;
        len = 0;
        if (left != -1) {
            last_new = ind;
            len = 1;
        }
    }

    int right() const {
        return len % 2 == 1 ? left : 1 - left;
    }

    void update(const Data& l, const Data& r) {
        if (l.len == 0) {
            len = r.len;
            left = r.left;
            last_new = r.last_new;
        } else if (r.len == 0) {
            len = l.len;
            left = l.left;
            last_new = l.last_new;
        } else {
            len = l.len + r.len - (l.right() == r.left);
            if (r.len == 1 && r.left == l.right()) {
                last_new = l.last_new;
            } else {
                last_new = r.last_new;
            }
            left = l.left;
            assert(right() == r.right());
        }
    }
};

struct Node {
    Node* l = nullptr;
    Node* r = nullptr;

    Data data;

    Node() {}
    Node(int x, int ind) : data(x, ind) {}

    void update() {
        assert(l != nullptr);
        assert(r != nullptr);
        data.update(l->data, r->data);
    }
};

OSTREAM(Node, len, left, last_new);

Node* build(int l, int r, const vector<int>& v) {
    if (l == r) {
        return new Node(v[l], l);
    }
    int m = (l + r) / 2;
    auto node = new Node();
    node->l = build(l, m, v);
    node->r = build(m + 1, r, v);
    node->update();
    return node;
}

Node* update(Node* node, int i, int val, int vl, int vr) {
    if (vl == vr) {
        return new Node(val, i);
    }
    auto root = new Node();
    root->l = node->l;
    root->r = node->r;
    int m = (vl + vr) / 2;
    if (i <= m) {
        root->l = update(node->l, i, val, vl, m);
    } else {
        root->r = update(node->r, i, val, m + 1, vr);
    }
    root->update();
    return root;
}

Data ask(Node* node, int l, int r, int vl, int vr) {
    if (l <= vl && vr <= r) {
        return node->data;
    }
    if (vr < l || vl > r) {
        return Data(-1, -1);
    }
    int m = (vl + vr) / 2;
    Data n;
    auto dl = ask(node->l, l, r, vl, m);
    auto dr = ask(node->r, l, r, m + 1, vr);

    n.update(dl, dr);
    return n;
}

vector<Node*> roots;
vector<int> ds;

void init(int n_, std::vector<int> h_) {
    n = n_;
    h = h_;
    h.pb(inf);
    n = h.size();
    roots.clear();
    ds.clear();

    sparse_min = SparseTable<int>(h, [](int a, int b) { return min(a, b); });
    sparse_max = SparseTable<int>(h, [](int a, int b) { return max(a, b); });
    hill.assign(n, -1);
    valley.assign(n, -1);
    vector<int> stup, stdown;
    for (int i = n - 1; i >= 0; --i) {
        while (!stup.empty() && h[stup.back()] < h[i])
            stup.pop_back();
        while (!stdown.empty() && h[stdown.back()] > h[i])
            stdown.pop_back();
        if (stup.empty()) {
            hill[i] = inf;
        } else {
            hill[i] = h[i] - sparse_min.ask(i, stup.back());
        }
        if (stdown.empty()) {
            valley[i] = inf;
        } else {
            valley[i] = -h[i] + sparse_max.ask(i, stdown.back());
        }

        stup.push_back(i);
        stdown.push_back(i);
    }

    vector<pair<int, int>> events;
    for (int i = 0; i < n; ++i) {
        if (hill[i] > 0) events.eb(hill[i], i);
        if (valley[i] > 0) events.eb(valley[i], i);
    }
    show(hill);
    show(valley);
    show(events);

    sort(events.begin(), events.end());
    reverse(events.begin(), events.end());

    ds.pb(inf + 1);
    roots.pb(build(0, n-1, vector<int>(n, -1)));

    int ind = 0;
    while (ind < events.size()) {
        shows;
        int r = ind;
        Node* next = roots.back();
        ds.pb(events[ind].first);
        show(ds.back());
        while (r < events.size() && events[r].first == events[ind].first) {
            int i = events[r].second;
            int val = (ds.back() <= hill[i] ? 1 : (ds.back() <= valley[i] ? 0 : -1));
            show(i, val);
            next = update(next, i, val, 0, n-1);
            ++r;
        }
        roots.pb(next);

        ind = r;
    }
}

int max_towers(int l, int r, int d) {
    if (l == r) return 1;

    int L = -1, R = ds.size();
    while (R - L > 1) {
        int C = (L + R) / 2;
        if (ds[C] >= d)
            L = C;
        else
            R = C;
    }
    show(ds);
    show(L);
    auto res = ask(roots[L], l, r-1, 0, n-1);
    int ans = 0;
    if (res.len > 0) {
        ans = res.len;
        if (res.left == 1) {
            --ans;
        }
        int last = res.last_new;
        if (ans % 2 == 0 && ans > 0 && sparse_min.ask(last + 1, r) <= h[last] - d)
            ++ans;
    }
    return max(1, (ans + 1) / 2);
}


#ifdef HOUSE

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int n, q;
    cin >> n >> q;
    vector<int> h(n);
    cin >> h;
    init(n, h);
    while (q--) {
        int l, r, d;
        cin >> l >> r >> d;
        cout << max_towers(l, r, d) << '\n';
    }

    return 0;
}
#endif

Compilation message (stderr)

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:250:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  250 |     while (ind < events.size()) {
      |            ~~~~^~~~~~~~~~~~~~~
towers.cpp:256:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  256 |         while (r < events.size() && events[r].first == events[ind].first) {
      |                ~~^~~~~~~~~~~~~~~
towers.cpp: In instantiation of 'void SparseTable<T, F>::build() [with T = int; F = std::function<int(const int&, const int&)>]':
towers.cpp:65:9:   required from 'SparseTable<T, F>::SparseTable(const std::vector<U>&, F) [with U = int; T = int; F = std::function<int(const int&, const int&)>]'
towers.cpp:209:76:   required from here
towers.cpp:70:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int i = 2; i < p2.size(); ++i)
      |                         ~~^~~~~~~~~~~
towers.cpp:72: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]
   72 |         for (int i = 1; i < table.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~
towers.cpp:73:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             for (int j = 0; j + (1 << i) <= table[i].size(); ++j) {
      |                             ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

• 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