Submission #712968

#	Time	Username	Problem	Language	Result	Execution time	Memory
712968		t6twotwo	Radio Towers (IOI22_towers)	C++17	41 / 100	4025 ms	14304 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, X = -1;
vector<int> H, pfs, lg;
vector<vector<int>> st;
int query(int l, int r) {
    int k = __lg(r - l);
    return max(st[l][k], st[r - (1 << k)][k]);
}
void init(int _N, vector<int> _H) {
    N = _N;
    H = _H;
    int L = 0, R = N - 1;
    while (L + 1 < N && H[L + 1] > H[L]) L++;
    while (R - 1 >= 0 && H[R - 1] > H[R]) R--;
    if (L == R) X = L;
    pfs.resize(N + 1);
    for (int i = 0; i < N; i++) {
        pfs[i + 1] = pfs[i];
        if ((i == 0 || H[i] < H[i - 1]) && (i == N - 1 || H[i] < H[i + 1])) {
            pfs[i + 1]++;
        }
    }
    int lg = __lg(N);
    st.assign(N, vector<int>(lg + 1));
    for (int i = 0; i < N; i++) {
        st[i][0] = H[i];
    }
    for (int j = 0; j < lg; j++) {
        for (int i = 0; i + (2 << j) <= N; i++) {
            st[i][j + 1] = max(st[i][j], st[i + (1 << j)][j]);
        }
    }
}
int subtask1(int L, int R, int D) {
    if (L < X && X < R && max(H[L], H[R]) <= H[X] - D) {
        return 2;
    } else {
        return 1;
    }
}
int subtask23(int L,int R, int D) {
    R++;
    vector<int> p(R - L);
    iota(p.begin(), p.end(), L);
    sort(p.begin(), p.end(), [&](int i, int j) {
        return H[i] < H[j];
    });
    set<int> s;
    int ans = 0;
    for (int i : p) {
        auto it = s.lower_bound(i);
        if (it != s.begin()) {
            int j = *prev(it);
            if (max(H[i], H[j]) > query(j, i + 1) - D) continue;
        }
        if (it != s.end()) {
            int j = *it;
            if (max(H[i], H[j]) > query(i, j + 1) - D) continue;
        }
        ans++;
        s.insert(i);
    }
    return ans;
}
int subtask4(int L, int R, int D) {
    if (L == R) return 1;
    int ans = pfs[R] - pfs[L + 1];
    if (H[L] < H[L + 1]) ans++;
    if (H[R] < H[R - 1]) ans++;
    return ans;
}
int max_towers(int L, int R, int D) {
    if (X != -1) return subtask1(L, R, D);
    if (D == 1) return subtask4(L, R, D);
    return subtask23(L, R, D);
}

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