oj.uz

Submission #711583

# Submission time Handle Problem Language Result Execution time Memory
711583 2023-03-17T09:18:32 Z t6twotwo Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 11884 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N;
vector<int> H, lg;
vector<vector<int>> st;
int f(int i, int j) {
    return H[i] > H[j] ? i : j;
}
int query(int l, int r) {
    int k = lg[r - l];
    return f(st[l][k], st[r - (1 << k)][k]);
}
void init(int _N, vector<int> _H) {
    N = _N;
    H = _H;
    lg.resize(N + 1);
    for (int i = 2; i <= N; i++) {
        lg[i] = lg[i / 2] + 1;
    }
    st.assign(N, vector<int>(lg[N] + 1));
    for (int i = 0; i < N; i++) {
        fill(st[i].begin(), st[i].end(), i);
    }
    for (int j = 0; j < lg[N]; j++) {
        for (int i = 0; i + (2 << j) <= N; j++) {
            st[i][j + 1] = f(st[i][j], st[i + (1 << j)][j]);
        }
    }
}
int max_towers(int L, int R, int D) { R++;
    auto dc = [&](auto dc, int l, int r) -> int {
        if (l >= r) return 0;
        int x = query(l, r);
        return max(1, (l + 1 == x ? 1 : dc(dc, l, x - 1)) + (r - 2 == x ? 1 : dc(dc, x + 1, r)));
    };
    return dc(dc, L, R);
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

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