oj.uz

Submission #838710

# Submission time Handle Problem Language Result Execution time Memory
838710 2023-08-27T15:46:00 Z erekle Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 12728 KB 
#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 max(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;

    int moves = 0;
    for (int i = firstBlock; i < (int)blocks.size(); ++i) {
        if (blocks[firstBlock].second <= blocks[i].first) {
            firstBlock = i;
            ++moves;
        }
    }

    // // 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 297 ms 5604 KB 15th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 464 KB 1st lines differ - on the 1st token, expected: '13', found: '40'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 464 KB 1st lines differ - on the 1st token, expected: '13', found: '40'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4016 ms 12728 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 397 ms 3276 KB 1st lines differ - on the 1st token, expected: '7197', found: '6270'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 464 KB 1st lines differ - on the 1st token, expected: '13', found: '40'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 297 ms 5604 KB 15th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -