oj.uz

Submission #682712

# Submission time Handle Problem Language Result Execution time Memory
682712 2023-01-16T20:28:14 Z SirCovidThe19th Radio Towers (IOI22_towers) C++17
17 / 100
 1238 ms 75836 KB 
#include <bits/stdc++.h>
using namespace std; 

const int mx = 1e5 + 5;

struct pstNode{
    int sum, mn, mx;
};
struct segNode{
    int mn, mx, dif1, dif2;
};

pstNode comb(pstNode a, pstNode b){
    return {a.sum + b.sum, min(a.mn, b.mn), max(a.mx, b.mx)};
};
segNode comb(segNode a, segNode b){
    return {min(a.mn, b.mn), max(a.mx, b.mx), max({a.dif1, b.dif1, b.mx - a.mn}), max({a.dif2, b.dif2, a.mx - b.mn})};
}

struct persistentSegTree{
    pstNode seg[mx * 31]; int idx = 1, lc[mx * 31] = {}, rc[mx * 31] = {};

    persistentSegTree(){ 
        fill(seg, seg + mx * 31, pstNode({0, int(1e9), 0})); 
    }
    void dup(int &i){
        lc[idx] = lc[i];
        rc[idx] = rc[i];
        seg[idx] = seg[i];
        i = idx; idx++;
    }
    void upd(int p, int &i, int l = 0, int r = mx){
        dup(i);
        if (l == r){ seg[i] = {1, l, l}; return; }

        int mid = (l + r) / 2;
        if (p <= mid) upd(p, lc[i], l, mid);
        else upd(p, rc[i], mid + 1, r);

        seg[i] = comb(seg[lc[i]], seg[rc[i]]);
    }
    pstNode qry(int ql, int qr, int i, int l = 0, int r = mx){
        if (qr < l or ql > r or !i) return {0, int(1e9), 0};
        if (l >= ql and r <= qr) return seg[i];
        int mid = (l + r) / 2;
        return comb(qry(ql, qr, lc[i], l, mid), qry(ql, qr, rc[i], mid + 1, r));
    }
};
struct segTree{
    segNode seg[mx * 2 + 5];

    void upd(int i, int val){
        seg[i += mx] = {val, val, 0, 0};
        for (i /= 2; i > 0; i /= 2) seg[i] = comb(seg[i * 2], seg[i * 2 + 1]);
    }
    segNode qry(int l, int r){ 
        segNode retL = segNode({int(1e9), 0, 0, 0});
        segNode retR = segNode({int(1e9), 0, 0, 0});

        for (l += mx, r += mx; l <= r; r /= 2, l /= 2){
            if (l % 2 == 1) retL = comb(retL, seg[l++]);
            if (r % 2 == 0) retR = comb(seg[r--], retR);
        }
        return comb(retL, retR);
    }
};
struct sparseTable{
    int rmq[mx][17];

    void build(vector<int> A){
        for (int j = 0; j < 17; j++)
            for (int i = 0; i + (1 << j) - 1 < A.size(); i++)
                rmq[i][j] = !j ? A[i] : max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
    }
    int qry(int l, int r){
        int lg = 31 - __builtin_clz(r - l + 1);
        return max(rmq[l][lg], rmq[r - (1 << lg) + 1][lg]);
    }
};

vector<int> H; map<int, int> root; segTree st; persistentSegTree pst; sparseTable fastMax;

int max_towers(int l, int r, int d){
    auto it = root.lower_bound(d);
    pstNode ret = pst.qry(l, r, it->second);
    if (ret.sum == 0) return 1;
    
    int lo = l, hi = ret.mn;
    while (lo < hi){
        int mid = (lo + hi + 1) / 2;
        (fastMax.qry(mid, ret.mn) >= H[ret.mn] + d ? lo = mid : hi = mid - 1); 
    }
    ret.sum += (H[lo] >= H[ret.mn] + d and st.qry(l, lo).dif1 >= d);

    lo = ret.mx, hi = r;
    while (lo < hi){
        int mid = (lo + hi) / 2;
        (fastMax.qry(ret.mx, mid) >= H[ret.mx] + d ? hi = mid : lo = mid + 1);
    }
    ret.sum += (H[hi] >= H[ret.mx] + d and st.qry(hi, r).dif2 >= d);
    return ret.sum;
}
void init(int n, vector<int> h_){
    H = h_;
    fastMax.build(H);

    int L[n], R[n]; 
    for (int i = 0; i < n; i++) L[i] = R[i] = -1;
    
    stack<int> stk;
    for (int i = 0; i < n; i++){
        st.upd(i, H[i]);
        while (stk.size() and H[stk.top()] >= H[i]){
            R[stk.top()] = i;
            stk.pop();
        }
        if (stk.size()) L[i] = stk.top();
        stk.push(i);
    }

    vector<pair<int, int>> V;
    for (int i = 0; i < n; i++){
        int dlim = 1e9;
        if (L[i] != -1) dlim = min(dlim, fastMax.qry(L[i], i) - H[i]);
        if (R[i] != -1) dlim = min(dlim, fastMax.qry(i, R[i]) - H[i]);
        V.push_back({dlim, i});
    }
    sort(V.begin(), V.end(), greater<pair<int, int>>());

    int curRoot = 1;
    for (auto [dlim, i] : V){
        pst.upd(i, curRoot);
        root[dlim] = curRoot;
    }
}

Compilation message

towers.cpp: In member function 'void sparseTable::build(std::vector<int>)':
towers.cpp:72:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for (int i = 0; i + (1 << j) - 1 < A.size(); i++)
      |                             ~~~~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 538 ms 68788 KB 12th 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 Correct 26 ms 61008 KB Output is correct
2 Correct 32 ms 61184 KB Output is correct
3 Correct 29 ms 61272 KB Output is correct
4 Correct 29 ms 61196 KB Output is correct
5 Correct 26 ms 61192 KB Output is correct
6 Correct 26 ms 61220 KB Output is correct
7 Correct 26 ms 61256 KB Output is correct
8 Correct 29 ms 61272 KB Output is correct
9 Correct 27 ms 61188 KB Output is correct
10 Correct 30 ms 61264 KB Output is correct
11 Correct 28 ms 61132 KB Output is correct
12 Incorrect 25 ms 61040 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 61008 KB Output is correct
2 Correct 32 ms 61184 KB Output is correct
3 Correct 29 ms 61272 KB Output is correct
4 Correct 29 ms 61196 KB Output is correct
5 Correct 26 ms 61192 KB Output is correct
6 Correct 26 ms 61220 KB Output is correct
7 Correct 26 ms 61256 KB Output is correct
8 Correct 29 ms 61272 KB Output is correct
9 Correct 27 ms 61188 KB Output is correct
10 Correct 30 ms 61264 KB Output is correct
11 Correct 28 ms 61132 KB Output is correct
12 Incorrect 25 ms 61040 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 960 ms 74864 KB Output is correct
2 Correct 1074 ms 75016 KB Output is correct
3 Correct 1238 ms 75132 KB Output is correct
4 Correct 998 ms 75828 KB Output is correct
5 Correct 1012 ms 75836 KB Output is correct
6 Correct 1018 ms 75704 KB Output is correct
7 Correct 1091 ms 75788 KB Output is correct
8 Correct 875 ms 74564 KB Output is correct
9 Correct 875 ms 74152 KB Output is correct
10 Correct 1070 ms 74428 KB Output is correct
11 Correct 1039 ms 74176 KB Output is correct
12 Incorrect 711 ms 74292 KB 170th lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 64324 KB Output is correct
2 Correct 1176 ms 75000 KB Output is correct
3 Correct 1061 ms 74936 KB Output is correct
4 Correct 1113 ms 75716 KB Output is correct
5 Correct 1082 ms 75836 KB Output is correct
6 Correct 1160 ms 75768 KB Output is correct
7 Correct 1075 ms 75796 KB Output is correct
8 Correct 955 ms 74548 KB Output is correct
9 Correct 1112 ms 74116 KB Output is correct
10 Correct 1025 ms 74344 KB Output is correct
11 Correct 947 ms 74176 KB Output is correct
12 Correct 105 ms 75024 KB Output is correct
13 Correct 115 ms 75772 KB Output is correct
14 Correct 111 ms 75800 KB Output is correct
15 Correct 75 ms 74152 KB Output is correct
16 Correct 81 ms 74412 KB Output is correct
17 Correct 114 ms 74568 KB Output is correct
18 Correct 107 ms 74948 KB Output is correct
19 Correct 105 ms 74940 KB Output is correct
20 Correct 139 ms 75708 KB Output is correct
21 Correct 115 ms 75712 KB Output is correct
22 Correct 109 ms 75836 KB Output is correct
23 Correct 111 ms 75708 KB Output is correct
24 Correct 79 ms 74560 KB Output is correct
25 Correct 82 ms 74132 KB Output is correct
26 Correct 78 ms 74428 KB Output is correct
27 Correct 76 ms 74156 KB Output is correct
28 Correct 25 ms 61264 KB Output is correct
29 Correct 27 ms 61312 KB Output is correct
30 Correct 31 ms 61216 KB Output is correct
31 Correct 25 ms 61208 KB Output is correct
32 Correct 27 ms 61184 KB Output is correct
33 Correct 24 ms 61096 KB Output is correct
34 Correct 25 ms 61264 KB Output is correct
35 Correct 29 ms 61248 KB Output is correct
36 Correct 29 ms 61268 KB Output is correct
37 Correct 25 ms 61276 KB Output is correct
38 Correct 26 ms 61364 KB Output is correct
39 Correct 33 ms 61244 KB Output is correct
40 Correct 26 ms 61216 KB Output is correct
41 Correct 25 ms 61256 KB Output is correct
42 Correct 26 ms 61256 KB Output is correct
43 Correct 25 ms 61156 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 61008 KB Output is correct
2 Correct 32 ms 61184 KB Output is correct
3 Correct 29 ms 61272 KB Output is correct
4 Correct 29 ms 61196 KB Output is correct
5 Correct 26 ms 61192 KB Output is correct
6 Correct 26 ms 61220 KB Output is correct
7 Correct 26 ms 61256 KB Output is correct
8 Correct 29 ms 61272 KB Output is correct
9 Correct 27 ms 61188 KB Output is correct
10 Correct 30 ms 61264 KB Output is correct
11 Correct 28 ms 61132 KB Output is correct
12 Incorrect 25 ms 61040 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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