oj.uz

Submission #755572

# Submission time Handle Problem Language Result Execution time Memory
755572 2023-06-10T11:13:49 Z MilosMilutinovic Radio Towers (IOI22_towers) C++17
17 / 100
 1091 ms 20248 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> vec;

namespace sparse {
    int n;
    vector<int> logs;
    vector<vector<int>> st;
    void build(vector<int> h) {
        n = (int) h.size();
        logs.resize(n + 1);
        st.resize(n);
        for (int i = 0; i < n; i++) {
            st[i].resize(20);
            st[i][0] = h[i];
        }
        for (int j = 1; j < 20; j++)
            for (int i = 0; i + (1 << j) <= n; i++)
                st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        for (int i = 2; i <= n; i++) logs[i] = logs[i >> 1] + 1;
    }
    int query(int l, int r) {
        int k = logs[r - l + 1];
        return max(st[l][k], st[r - (1 << k) + 1][k]);
    }
};

void init(int n, vector<int> h) {
    vector<int> l_id(n), r_id(n);
    vector<int> stk;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && h[i] < h[stk.back()]) {
            stk.pop_back();
        }
        l_id[i] = (stk.empty() ? -1 : stk.back());
        stk.push_back(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!stk.empty() && h[i] < h[stk.back()]) {
            stk.pop_back();
        }
        r_id[i] = (stk.empty() ? -1 : stk.back());
        stk.push_back(i);
    }
    sparse::build(h);
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) { return h[i] < h[j]; });
    for (int _i = 1; _i < n; _i++) {
        int i = order[_i];
        int d = 1e9;
        if (l_id[i] != -1)
            d = min(d, sparse::query(l_id[i], i) - h[i]);
        if (r_id[i] != -1)
            d = min(d, sparse::query(i, r_id[i]) - h[i]);
//        assert(d != 0);
//        printf("%d %d\n", i + 1, d);
        vec.push_back({d, i, l_id[i], r_id[i]});
    }
    sort(vec.begin(), vec.end());
}

int find_first(int x) {
    int l = 0, r = vec.size() - 1, p = vec.size();
    while (l <= r) {
        int mid = l + r >> 1;
        if (vec[mid][0] >= x)
            r = mid - 1, p = mid;
        else
            l = mid + 1;
    }
    return vec.size() - p;
}

int max_towers(int l, int r, int d) {
    return find_first(d) + 1;
}


/*
7 1
10 20 60 40 50 30 70
0 6 17
*/

Compilation message

towers.cpp: In function 'int find_first(int)':
towers.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 712 ms 19624 KB 1st lines differ - on the 1st token, expected: '11903', found: '33010'
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 4908 KB Output is correct
2 Correct 1010 ms 19864 KB Output is correct
3 Correct 691 ms 19860 KB Output is correct
4 Correct 1091 ms 19844 KB Output is correct
5 Correct 962 ms 19744 KB Output is correct
6 Correct 991 ms 19788 KB Output is correct
7 Correct 1065 ms 19844 KB Output is correct
8 Correct 1008 ms 20248 KB Output is correct
9 Correct 908 ms 20148 KB Output is correct
10 Correct 769 ms 20168 KB Output is correct
11 Correct 942 ms 20200 KB Output is correct
12 Correct 83 ms 19852 KB Output is correct
13 Correct 88 ms 19744 KB Output is correct
14 Correct 84 ms 19864 KB Output is correct
15 Correct 54 ms 20144 KB Output is correct
16 Correct 64 ms 19976 KB Output is correct
17 Correct 82 ms 19228 KB Output is correct
18 Correct 95 ms 19872 KB Output is correct
19 Correct 86 ms 19876 KB Output is correct
20 Correct 87 ms 19824 KB Output is correct
21 Correct 92 ms 19744 KB Output is correct
22 Correct 86 ms 19740 KB Output is correct
23 Correct 90 ms 19872 KB Output is correct
24 Correct 50 ms 20144 KB Output is correct
25 Correct 47 ms 20232 KB Output is correct
26 Correct 68 ms 20120 KB Output is correct
27 Correct 55 ms 20236 KB Output is correct
28 Correct 1 ms 592 KB Output is correct
29 Correct 1 ms 592 KB Output is correct
30 Correct 1 ms 592 KB Output is correct
31 Correct 1 ms 592 KB Output is correct
32 Correct 1 ms 592 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 592 KB Output is correct
35 Correct 2 ms 592 KB Output is correct
36 Correct 1 ms 592 KB Output is correct
37 Correct 2 ms 592 KB Output is correct
38 Correct 1 ms 592 KB Output is correct
39 Correct 2 ms 592 KB Output is correct
40 Correct 1 ms 592 KB Output is correct
41 Correct 1 ms 592 KB Output is correct
42 Correct 1 ms 592 KB Output is correct
43 Correct 1 ms 592 KB Output is correct

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

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