oj.uz

Submission #682717

# Submission time Handle Problem Language Result Execution time Memory
682717 2023-01-16T20:37:34 Z SirCovidThe19th Radio Towers (IOI22_towers) C++17
17 / 100
 1322 ms 75844 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;
        (st.qry(mid, ret.mn).mx >= 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;
        (st.qry(ret.mx, mid).mx >= 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 403 ms 68768 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 27 ms 61264 KB Output is correct
3 Correct 27 ms 61252 KB Output is correct
4 Correct 30 ms 61212 KB Output is correct
5 Correct 28 ms 61244 KB Output is correct
6 Correct 30 ms 61196 KB Output is correct
7 Correct 27 ms 61260 KB Output is correct
8 Correct 26 ms 61260 KB Output is correct
9 Correct 27 ms 61264 KB Output is correct
10 Correct 27 ms 61204 KB Output is correct
11 Correct 27 ms 61264 KB Output is correct
12 Incorrect 26 ms 60900 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 27 ms 61264 KB Output is correct
3 Correct 27 ms 61252 KB Output is correct
4 Correct 30 ms 61212 KB Output is correct
5 Correct 28 ms 61244 KB Output is correct
6 Correct 30 ms 61196 KB Output is correct
7 Correct 27 ms 61260 KB Output is correct
8 Correct 26 ms 61260 KB Output is correct
9 Correct 27 ms 61264 KB Output is correct
10 Correct 27 ms 61204 KB Output is correct
11 Correct 27 ms 61264 KB Output is correct
12 Incorrect 26 ms 60900 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 936 ms 74880 KB Output is correct
2 Correct 1041 ms 75028 KB Output is correct
3 Correct 1227 ms 75020 KB Output is correct
4 Correct 1074 ms 75844 KB Output is correct
5 Correct 1068 ms 75804 KB Output is correct
6 Correct 1208 ms 75752 KB Output is correct
7 Correct 1059 ms 75832 KB Output is correct
8 Correct 897 ms 74696 KB Output is correct
9 Correct 1008 ms 74176 KB Output is correct
10 Correct 1096 ms 74408 KB Output is correct
11 Correct 1035 ms 74208 KB Output is correct
12 Incorrect 547 ms 74272 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 286 ms 64316 KB Output is correct
2 Correct 1066 ms 74988 KB Output is correct
3 Correct 1186 ms 74940 KB Output is correct
4 Correct 1128 ms 75804 KB Output is correct
5 Correct 1067 ms 75828 KB Output is correct
6 Correct 1054 ms 75752 KB Output is correct
7 Correct 1176 ms 75776 KB Output is correct
8 Correct 1118 ms 74560 KB Output is correct
9 Correct 1322 ms 74152 KB Output is correct
10 Correct 870 ms 74332 KB Output is correct
11 Correct 1070 ms 74148 KB Output is correct
12 Correct 109 ms 75024 KB Output is correct
13 Correct 148 ms 75756 KB Output is correct
14 Correct 119 ms 75812 KB Output is correct
15 Correct 78 ms 74152 KB Output is correct
16 Correct 82 ms 74388 KB Output is correct
17 Correct 110 ms 74672 KB Output is correct
18 Correct 109 ms 74932 KB Output is correct
19 Correct 104 ms 74940 KB Output is correct
20 Correct 109 ms 75716 KB Output is correct
21 Correct 125 ms 75840 KB Output is correct
22 Correct 126 ms 75704 KB Output is correct
23 Correct 109 ms 75812 KB Output is correct
24 Correct 79 ms 74556 KB Output is correct
25 Correct 81 ms 74136 KB Output is correct
26 Correct 84 ms 74344 KB Output is correct
27 Correct 80 ms 74228 KB Output is correct
28 Correct 26 ms 61228 KB Output is correct
29 Correct 27 ms 61212 KB Output is correct
30 Correct 29 ms 61264 KB Output is correct
31 Correct 29 ms 61256 KB Output is correct
32 Correct 32 ms 61160 KB Output is correct
33 Correct 31 ms 61136 KB Output is correct
34 Correct 33 ms 61240 KB Output is correct
35 Correct 34 ms 61200 KB Output is correct
36 Correct 27 ms 61280 KB Output is correct
37 Correct 28 ms 61224 KB Output is correct
38 Correct 28 ms 61224 KB Output is correct
39 Correct 34 ms 61240 KB Output is correct
40 Correct 28 ms 61140 KB Output is correct
41 Correct 27 ms 61176 KB Output is correct
42 Correct 27 ms 61184 KB Output is correct
43 Correct 27 ms 61264 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 27 ms 61264 KB Output is correct
3 Correct 27 ms 61252 KB Output is correct
4 Correct 30 ms 61212 KB Output is correct
5 Correct 28 ms 61244 KB Output is correct
6 Correct 30 ms 61196 KB Output is correct
7 Correct 27 ms 61260 KB Output is correct
8 Correct 26 ms 61260 KB Output is correct
9 Correct 27 ms 61264 KB Output is correct
10 Correct 27 ms 61204 KB Output is correct
11 Correct 27 ms 61264 KB Output is correct
12 Incorrect 26 ms 60900 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 403 ms 68768 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -