Submission #1224723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224723		Sharky	Radio Towers (IOI22_towers)	C++20	23 / 100	4096 ms	11164 KiB

towers

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

int n, mx = 0, pos = 0;
vector<int> h;

const int N = 1e5 + 5;

int sp[19][N], lg2[N];

int query(int x, int y) {
    int j = lg2[y - x + 1];
    return max(sp[j][x], sp[j][y - (1 << j) + 1]);
}

void init(int _n, std::vector<int> H) {
    h = H;
    lg2[1] = 0;
    for (int i = 2; i <= n; i++) lg2[i] = lg2[i / 2] + 1;
}

int max_towers(int L, int R, int D) {
    vector<int> a;
    vector<pair<int, int>> srt;
    for (int i = L; i <= R; i++) a.push_back(h[i]);
    n = a.size();
    for (int i = 0; i < n; i++) sp[0][i] = a[i], srt.push_back({a[i], i});
    sort(srt.begin(), srt.end());
    lg2[1] = 0;
    for (int i = 2; i <= n; i++) lg2[i] = lg2[i / 2] + 1;
    for (int i = 1; i < 19; i++) {
        for (int j = 0; j + (1 << i) - 1 < n; j++) {
            sp[i][j] = max(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
        }
    }
    set<int> idx;
    int ans = 0;
    for (int i = 0; i < srt.size(); i++) {
        int x = srt[i].second;
        bool gone_wrong = 0;
        if (!idx.empty() && *idx.begin() < x) {
            int k = *--idx.lower_bound(x);
            if (query(k, x - 1) < a[x] + D) gone_wrong = 1;
        }
        if (!gone_wrong && !idx.empty() && *idx.rbegin() > x) {
            int k = *idx.lower_bound(x);
            if (query(x + 1, k) < a[x] + D) gone_wrong = 1;
        }
        if (!gone_wrong) {
            ans++;
            idx.insert(x);
        }
    }
    return ans;
}

• 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