Submission #836531

#	Time	Username	Problem	Language	Result	Execution time	Memory
836531		tengiz05	Radio Towers (IOI22_towers)	C++17	23 / 100	4097 ms	9280 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;

vector<int> h;
int n;
void init(int N, vector<int> H) {
    n = N;
    h = H;
}

struct SegmentTree {
    int n;
    vector<int> f;
    SegmentTree(int n) : n(n), f(4 * n) {}
    void modify(int p, int l, int r, int x, int y) {
        if (l == r - 1) {
            f[p] = y;
        } else {
            int m = (l + r) / 2;
            if (x < m) {
                modify(2 * p, l, m, x, y);
            } else {
                modify(2 * p + 1, m, r, x, y);
            }
            f[p] = max(f[2 * p], f[2 * p + 1]);
        }
    }
    void modify(int x, int y) {
        modify(1, 0, n, x, y);
    }
    int rangeMax(int p, int l, int r, int x, int y) {
        if (r <= x || y <= l) return 0;
        if (x <= l && r <= y) return f[p];
        int m = (l + r) / 2;
        return max(rangeMax(2 * p, l, m, x, y), rangeMax(2 * p + 1, m, r, x, y));
    }
    int rangeMax(int l, int r) {
        return rangeMax(1, 0, n, l, r);
    }
};

int max_towers(int l, int r, int D) {
    deque<pair<int, int>> st;
    vector<int> nxt(n, -1);
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && h[st.front().second] <= h[i]) st.pop_front();
        st.push_front({h[i], i});
        auto p = lower_bound(st.begin(), st.end(), pair{h[i] + D, -1});
        if (p != st.end()) {
            nxt[i] = p->second;
        }
    }
    st.clear();
    vector<int> prev(n, -1);
    for (int i = 0; i < n; i++) {
        while (!st.empty() && h[st.front().second] <= h[i]) st.pop_front();
        st.push_front({h[i], i});
        auto p = lower_bound(st.begin(), st.end(), pair{h[i] + D, -1});
        if (p != st.end()) {
            prev[i] = p->second;
        }
    }
    vector<vector<int>> events(n);
    vector<int> dp(n);
    for (int i = l; i <= r; i++) {
        if (nxt[i] != -1) {
            events[nxt[i]].push_back(i);
        }
    }
    SegmentTree s(n);
    for (int i = l; i <= r; i++) {
        // dp[i] = 1;
        // for (int j = l; j < i; j++) {
            // if (nxt[j] != -1 && prev[i] != -1 && nxt[j] < i && prev[i] > j) {
                // dp[i] = max(dp[i], dp[j] + 1);
            // }
        // }
        dp[i] = s.rangeMax(l, prev[i]) + 1;
        for (auto j : events[i]) {
            s.modify(j, dp[j]);
        }
    }
    return *max_element(dp.begin(), dp.end());
}

• Subtask 1: 0 / 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