oj.uz

Submission #682708

# Submission time Handle Problem Language Result Execution time Memory
682708 2023-01-16T20:14:28 Z SirCovidThe19th Radio Towers (IOI22_towers) C++17
0 / 100
 844 ms 74920 KB 
#include <bits/stdc++.h>
#include "towers.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 ret = segNode({int(1e9), 0, 0, 0});
        for (l += mx, r += mx; l <= r; r /= 2, l /= 2){
            if (l % 2 == 1) ret = comb(ret, seg[l++]);
            if (r % 2 == 0) ret = comb(seg[r--], ret);
        }
        return ret;
    }
};
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:71:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for (int i = 0; i + (1 << j) - 1 < A.size(); i++)
      |                             ~~~~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 374 ms 68836 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 Incorrect 31 ms 61044 KB 1st lines differ - on the 1st token, expected: '13', found: '14'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 844 ms 74920 KB 4th lines differ - on the 1st token, expected: '13956', found: '13957'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

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