Submission #1078866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078866		The_Samurai	Radio Towers (IOI22_towers)	C++17	0 / 100	700 ms	20536 KiB

towers

#include "towers.h"
#include "bits/stdc++.h"
using namespace std;

struct segtree {
    vector<pair<int, int>> tree;
    int size;

    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree.assign(2 * size, make_pair(0, 0));
    }

    void upd(int i, pair<int, int> v) {
        i += size;
        tree[i] = max(tree[i], v);
        for (; i > 1; i >>= 1) tree[i >> 1] = max(tree[i], tree[i ^ 1]);
    }

    pair<int, int> get(int l, int r) {
        if (l > r) return make_pair(0, 0);
        pair<int, int> res = make_pair(0, 0);
        for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = max(res, tree[l++]);
            if (r & 1) res = max(res, tree[--r]);
        }
        return res;
    }
};

int n;
vector<int> a;
segtree sg1, sg2;
const int lg = 17;
vector<vector<int>> jump;
set<pair<int, int>, greater<>> st;

void init(int _n, std::vector<int> _a) {
    n = _n;
    a = _a;
    jump = vector(lg + 1, vector(n, -1));
    st.clear();
    vector<int> all, v;
    for (int i = 0; i < n; i++) {
        all.emplace_back(a[i]);
        all.emplace_back(a[i] + 1);
    }
    sort(all.begin(), all.end());
    for (int i = 0; i < all.size(); i++) {
        if (i > 0 and all[i] == all[i - 1]) continue;
        v.emplace_back(all[i]);
    }
    int z = all.size();
    sg1.init(z + 1); sg2.init(z + 1);

    for (int i = 0; i < n; i++) {
        int pos = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
        int pos2 = lower_bound(v.begin(), v.end(), a[i] + 1) - v.begin();
        auto it = sg1.get(pos2, z);
        if (it.first > 0) jump[0][i] = it.second;
        it.second = i;
        it.first++;
        sg2.upd(pos2, it);
        sg1.upd(pos, sg2.get(0, pos));
    }
    for (int i = 1; i < n; i++) {
        if (jump[0][i] == -1) continue;
        for (int j = 1; j < lg; j++) {
            jump[j][i] = jump[j - 1][jump[j - 1][i]];
            if (jump[j][i] == -1) break;
        }
    }
    for (int l = 0, r = 0; r < n; r++) {
        if (r == n - 1 or a[r] > a[r + 1]) {
            st.emplace(l, r);
            l = r + 1;
        }
    }
}

int max_towers(int l, int r, int d) {
    auto it = st.upper_bound(make_pair(r, (int) 1e9));
    if (l > it->first) return 1;
    int i = it->first, ans = 1;
    for (int j = lg - 1; j >= 0; j--) {
        if (jump[j][i] < l) continue;
        ans += 1 << j;
        i = jump[j][i];
    }
    return ans;
}

Compilation message (stderr)

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i < all.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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