Submission #838724

#	Time	Username	Problem	Language	Result	Execution time	Memory
838724		erekle	Radio Towers (IOI22_towers)	C++17	56 / 100	874 ms	13896 KiB

towers

#include "towers.h"
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> H;

const int MX_N = 1e5, LG = 17;
int rmq[1+LG][MX_N];
int p2[MX_N];
int rangeMin(int l, int r) {
    int p = p2[r-l+1];
    return min(rmq[p][l], rmq[p][r-(1<<p)+1]);
}

void init(int N, vector<int> Hs) {
    for (int i = 2; i <= N; ++i) p2[i] = p2[i-1] + !(i & (i-1));

    n = N, H = Hs;
    // rmq
    for (int i = 0; i < n; ++i) rmq[0][i] = H[i];
    for (int i = 1, p = 1; i <= LG; ++i, p <<= 1) {
        for (int j = 0; j < n; ++j) {
            if (j+p >= n) rmq[i][j] = rmq[i-1][j];
            else rmq[i][j] = min(rmq[i-1][j], rmq[i-1][j+p]);
        }
    }
}

vector<pair<int, int>> blocks;
int nxt[1+LG][1+MX_N]; // binary lifting - next block

void init2(int D) {
    vector<pair<int, int>> b;
    for (int i = 0; i < n; ++i) {
        int L, R;
        { // find closest before
            int left = -1, right = i;
            while (left+1 < right) {
                int mid = (left + right) / 2;
                if (rangeMin(mid, i-1) <= H[i]-D) left = mid;
                else right = mid;
            }
            L = left;
        }
        { // find closest after
            int left = i, right = n;
            while (left+1 < right) {
                int mid = (left + right) / 2;
                if (rangeMin(i+1, mid) <= H[i]-D) right = mid;
                else left = mid;
            }
            R = right;
        }
        if (0 <= L && R < n) b.emplace_back(L, R);
    }

    // erase blocks with other blocks inside them
    sort(b.begin(), b.end());
    for (int i = (int)b.size()-1, minEnd = n; i >= 0; --i) {
        if (b[i].second < minEnd) minEnd = b[i].second, blocks.push_back(b[i]);
    }
    reverse(blocks.begin(), blocks.end());

    // find next block for each block
    for (size_t i = 0, j = 0; i < blocks.size(); ++i) {
        while (j < blocks.size() && blocks[j].first < blocks[i].second) ++j;
        nxt[0][i] = j;
    }
    nxt[0][blocks.size()] = blocks.size();

    // build binary lifting
    for (int i = 1; i <= LG; ++i) {
        for (int j = 0; j <= (int)blocks.size(); ++j) nxt[i][j] = nxt[i-1][nxt[i-1][j]];
    }
}

bool hadQuery = false;
int max_towers(int L, int R, int D) { // case: constant D
    if (!hadQuery) init2(D), hadQuery = true;

    int firstBlock = lower_bound(blocks.begin(), blocks.end(), pair<int, int>{L, 0}) - blocks.begin();
    if (firstBlock == (int)blocks.size() || blocks[firstBlock].second > R) return 1;

    // find furthest descendant of firstBlock that ends before R
    int lastBlock = firstBlock;
    int moves = 0;
    for (int i = LG; i >= 0; --i) {
        int b = nxt[i][lastBlock];
        if (b < (int)blocks.size() && blocks[b].second <= R) lastBlock = b, moves += 1 << i;
    }
    return moves + 2; // moves + 1 blocks, so moves + 2 gaps between and around blocks
}

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