oj.uz

Submission #796464

# Submission time Handle Problem Language Result Execution time Memory
796464 2023-07-28T12:11:08 Z drdilyor Radio Towers (IOI22_towers) C++17
17 / 100
 1943 ms 37948 KB 
#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
using ll = long long;
constexpr int inf = 1e9;

template<typename T, typename Op>
struct SparseTable {
    vector<vector<T>> sparse;
    Op accum_func;

    SparseTable() = default;

    SparseTable(const vector<T>& arr, const Op func) : accum_func(func) {
        int n = arr.size();
        int logn = 32 - __builtin_clz(n);
        sparse.resize(logn, vector<T>(n));
        sparse[0] = arr;
        for (int lg = 1; lg < logn; lg++) {
            for (int i = 0; i + (1 << lg) <= n; i++) {
                sparse[lg][i] = accum_func(sparse[lg - 1][i], sparse[lg - 1][i + (1 << (lg - 1))]);
            }
        }
    }

    T find(int l, int r) { // [l, r]
        r++;
        int cur_log = 31 - __builtin_clz(r - l);
        return accum_func(sparse[cur_log][l], sparse[cur_log][r - (1 << cur_log)]);
    }
};

struct SegmentTree {
    using T = vector<int>;
    using S = int;
    const T id = {};
    inline T single(S v) { return {v}; }

    T merge(const T& l, const T& r) {
        T res(l.size() + r.size());
        std::merge(l.cbegin(), l.cend(),
              r.cbegin(), r.cend(),
              res.begin());
        return res;
    }

    int n;
    vector<T> tree;

    SegmentTree() = default;
    void init(vector<S> arr) {
        n = arr.size();
        while (n & (n-1)) n++;
        tree.resize(n * 2, id);
        for (int i = 0; i < (int)arr.size(); i++) {
            tree[i + n] = single(arr[i]);
        }
        build();
    }

    void build() {
        for (int i = n-1; i >= 1; i--) {
            tree[i] = merge(tree[i*2], tree[i*2 + 1]);
        }
    }

    void update(int i, S v) {
        tree[i+=n] = single(v);
        for (i /= 2; i >= 1; i/= 2)
            tree[i] = merge(tree[i*2], tree[i*2+1]);
    }

    int query(int l, int r, int x) {
        int cnt = 0;
        l += n; r += n;
        while (l <= r) {
            if (l % 2 == 1) {
                cnt += count_ge(tree[l++], x);
            }
            if (r % 2 == 0) {
                cnt += count_ge(tree[r--], x);
            }
            l /= 2; r /= 2;
        }
        return cnt;
    }

    int count_ge(T& v, int x) {
        return v.end() - lower_bound(v.begin(), v.end(), x);
    }

    int leftmost(int v, int x) {
        if (tree[v].back() < x) return -1;
        while (v < n) {
            if (tree[v*2].back() >= x) v = v * 2;
            else v = v * 2 + 1;
        }
        return v - n;
    }

    int rightmost(int v, int x) {
        if (tree[v].back() < x) return -1;
        while (v < n) {
            if (tree[v*2+1].size() && tree[v*2+1].back() >= x) v = v * 2 + 1;
            else v = v * 2;
        }
        return v - n;
    }


    int find_leftmost(int l, int r, int x, int v, int tl, int tr) {
        if (l <= tl && tr <= r) return leftmost(v, x);
        if (tr < l || r < tl) return -1;
        int mid = (tl+tr) / 2;
        int ans = find_leftmost(l, r, x, v * 2, tl, mid);
        if (ans != -1) return ans;
        return find_leftmost(l, r, x, v * 2 + 1, mid+1, tr);
    }

    int find_rightmost(int l, int r, int x, int v, int tl, int tr) {
        if (l <= tl && tr <= r) return rightmost(v, x);
        if (tr < l || r < tl) return -1;
        int mid = (tl+tr) / 2;
        int ans = find_rightmost(l, r, x, v * 2 + 1, mid+1, tr);
        if (ans != -1) return ans;
        return find_rightmost(l, r, x, v * 2, tl, mid);
    }

    int find_leftmost(int l, int r, int x) {
        return find_leftmost(l, r, x, 1, 0, n-1);
    }
    int find_rightmost(int l, int r, int x) {
        return find_rightmost(l, r, x, 1, 0, n-1);
    }
};

struct SegmentTree2 {
    struct Node {
        int mxd = -1;
        int mxr = -1;
        int mn = 0;
        int mx = 0;
    };
    Node merge(Node& a, Node& b) {
        if (a.mxd == -1) return b;
        if (b.mxd == -1) return a;
        return {
            .mxd = max({0, a.mxd, b.mxd, b.mx - a.mn}),
            .mxr = max({0, a.mxr, b.mxr, a.mx - b.mn}),
            .mn = min(a.mn, b.mn),
            .mx = max(a.mx, b.mx),
        };
    }

    Node single(int x) {
        return {0, 0, x, x};
    }

    int n;
    vector<Node> tree;

    SegmentTree2() = default;
    void init(vector<int> arr) {
        n = arr.size();
        while (n & (n-1)) n++;
        tree.resize(n * 2, {});
        for (int i = 0; i < (int)arr.size(); i++) {
            tree[i + n] = single(arr[i]);
        }
        build();
    }

    void build() {
        for (int i = n-1; i >= 1; i--) {
            tree[i] = merge(tree[i*2], tree[i*2 + 1]);
        }
    }

    void update(int i, int v) {
        tree[i+=n] = single(v);
        for (i /= 2; i >= 1; i/= 2)
            tree[i] = merge(tree[i*2], tree[i*2+1]);
    }

    Node query(int l, int r) {
        Node left, right;
        l += n; r += n;
        while (l <= r) {
            if (l % 2 == 1) left = merge(left, tree[l++]);
            if (r % 2 == 0) right = merge(tree[r--], right);
            l /= 2; r /= 2;
        }
        return merge(left, right);
    }
};


int st_min(int a, int b) { return min(a, b); }
int st_max(int a, int b) { return max(a, b); }

int n;
vector<int> h, ix;
SparseTable<int, decltype(&st_min)> hmax;
SparseTable<int, decltype(&st_max)> hmin;

vector<int> start;
SegmentTree ans;
SegmentTree2 delta;

int find_left(int i, int d) {
    int l = -1, r = i;
    while (l < r-1) {
        int mid = (l+r) / 2;
        if (hmax.find(mid, i) - h[i] >= d)
            l = mid;
        else r = mid;
    }
    return l;
}

int find_right(int i, int d) {
    int l = i, r = n;
    while (l < r-1) {
        int mid = (l+r) / 2;
        if (hmax.find(i, mid) - h[i] >= d)
            r = mid;
        else l = mid;
    }
    return r;
}

void init(int N, std::vector<int> H) {
    n = N, h = H;
    ix.resize(n);
    start.resize(n);
    iota(ix.begin(), ix.end(), 0);
    sort(ix.begin(), ix.end(), [&](int i, int j) {
            return h[i] < h[j];
            });
    hmax = SparseTable(h, st_max);
    hmin = SparseTable(h, st_min);
    for (int i = 0; i < n;i++) {
        int lD = 0, rD = inf+1;
        while (lD < rD-1) {
            int D = (lD + rD) / 2;
            bool ok = 1;

            int lg = find_left(i, D);
            if (hmin.find(lg+1, i) < h[i]) ok = 0;

            int rg = find_right(i, D);
            if (hmin.find(i, rg-1) < h[i]) ok = 0;

            if (ok) lD = D;
            else rD = D;
        }
        start[i] = lD;
    }
    ans.init(start);
    delta.init(h);
    // for (int i : H) cout << i << ' '; cout << endl;
    // for (int i : start) cout << i << ' '; cout << endl;
}

int max_towers(int L, int R, int D) {
    int cnt = ans.query(L, R, D);
    int left = ans.find_leftmost(L, R, D);
    int right = ans.find_rightmost(L, R, D);
    int lg = left == -1 ? -1 : find_left(left, D);
    int rg = right == -1 ? n : find_right(right, D);
    // cout << cnt << ' ' << left << ' ' << right << '\n';
    // cout << lg << ' ' << rg << endl;
    if (lg > L && delta.query(L, lg).mxd >= D) cnt++;
    if (rg < R && delta.query(rg, R).mxr >= D) cnt++;
    return max(1, cnt);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 766 ms 21120 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 2 ms 336 KB Output is correct
2 Correct 10 ms 768 KB Output is correct
3 Correct 10 ms 848 KB Output is correct
4 Correct 10 ms 848 KB Output is correct
5 Correct 11 ms 768 KB Output is correct
6 Correct 10 ms 848 KB Output is correct
7 Correct 10 ms 848 KB Output is correct
8 Correct 10 ms 772 KB Output is correct
9 Correct 10 ms 848 KB Output is correct
10 Correct 12 ms 848 KB Output is correct
11 Correct 10 ms 796 KB Output is correct
12 Incorrect 1 ms 208 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 2 ms 336 KB Output is correct
2 Correct 10 ms 768 KB Output is correct
3 Correct 10 ms 848 KB Output is correct
4 Correct 10 ms 848 KB Output is correct
5 Correct 11 ms 768 KB Output is correct
6 Correct 10 ms 848 KB Output is correct
7 Correct 10 ms 848 KB Output is correct
8 Correct 10 ms 772 KB Output is correct
9 Correct 10 ms 848 KB Output is correct
10 Correct 12 ms 848 KB Output is correct
11 Correct 10 ms 796 KB Output is correct
12 Incorrect 1 ms 208 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 1748 ms 37724 KB Output is correct
2 Correct 1942 ms 37856 KB Output is correct
3 Correct 1943 ms 37948 KB Output is correct
4 Correct 1872 ms 37864 KB Output is correct
5 Correct 1873 ms 37860 KB Output is correct
6 Correct 1801 ms 37904 KB Output is correct
7 Correct 1809 ms 37872 KB Output is correct
8 Correct 1746 ms 37864 KB Output is correct
9 Correct 1512 ms 37912 KB Output is correct
10 Correct 1741 ms 37852 KB Output is correct
11 Correct 1663 ms 37856 KB Output is correct
12 Incorrect 1767 ms 37860 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 501 ms 8848 KB Output is correct
2 Correct 1638 ms 37860 KB Output is correct
3 Correct 1754 ms 37860 KB Output is correct
4 Correct 1669 ms 37868 KB Output is correct
5 Correct 1701 ms 37860 KB Output is correct
6 Correct 1591 ms 37860 KB Output is correct
7 Correct 1719 ms 37860 KB Output is correct
8 Correct 1706 ms 37860 KB Output is correct
9 Correct 1564 ms 37888 KB Output is correct
10 Correct 1632 ms 37864 KB Output is correct
11 Correct 1601 ms 37856 KB Output is correct
12 Correct 845 ms 37856 KB Output is correct
13 Correct 826 ms 37860 KB Output is correct
14 Correct 818 ms 37860 KB Output is correct
15 Correct 767 ms 37856 KB Output is correct
16 Correct 772 ms 37864 KB Output is correct
17 Correct 783 ms 36996 KB Output is correct
18 Correct 826 ms 37868 KB Output is correct
19 Correct 812 ms 37860 KB Output is correct
20 Correct 828 ms 37856 KB Output is correct
21 Correct 821 ms 37936 KB Output is correct
22 Correct 823 ms 37864 KB Output is correct
23 Correct 838 ms 37860 KB Output is correct
24 Correct 760 ms 37872 KB Output is correct
25 Correct 787 ms 37852 KB Output is correct
26 Correct 782 ms 37916 KB Output is correct
27 Correct 813 ms 37904 KB Output is correct
28 Correct 10 ms 848 KB Output is correct
29 Correct 10 ms 848 KB Output is correct
30 Correct 10 ms 848 KB Output is correct
31 Correct 10 ms 768 KB Output is correct
32 Correct 10 ms 768 KB Output is correct
33 Correct 4 ms 512 KB Output is correct
34 Correct 10 ms 848 KB Output is correct
35 Correct 10 ms 848 KB Output is correct
36 Correct 10 ms 848 KB Output is correct
37 Correct 10 ms 772 KB Output is correct
38 Correct 10 ms 848 KB Output is correct
39 Correct 12 ms 768 KB Output is correct
40 Correct 9 ms 848 KB Output is correct
41 Correct 10 ms 848 KB Output is correct
42 Correct 10 ms 768 KB Output is correct
43 Correct 10 ms 768 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 10 ms 768 KB Output is correct
3 Correct 10 ms 848 KB Output is correct
4 Correct 10 ms 848 KB Output is correct
5 Correct 11 ms 768 KB Output is correct
6 Correct 10 ms 848 KB Output is correct
7 Correct 10 ms 848 KB Output is correct
8 Correct 10 ms 772 KB Output is correct
9 Correct 10 ms 848 KB Output is correct
10 Correct 12 ms 848 KB Output is correct
11 Correct 10 ms 796 KB Output is correct
12 Incorrect 1 ms 208 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 766 ms 21120 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -