oj.uz

Submission #796456

# Submission time Handle Problem Language Result Execution time Memory
796456 2023-07-28T12:03:13 Z drdilyor Radio Towers (IOI22_towers) C++17
17 / 100
 1734 ms 38032 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(right, tree[r--]);
            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);
}

Compilation message

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:269:9: warning: unused variable 'lg' [-Wunused-variable]
  269 |     int lg = left == -1 ? -1 : find_left(left, D);
      |         ^~
towers.cpp:270:9: warning: unused variable 'rg' [-Wunused-variable]
  270 |     int rg = right == -1 ? n : find_right(right, D);
      |         ^~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 874 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 3 ms 336 KB Output is correct
2 Correct 11 ms 848 KB Output is correct
3 Correct 10 ms 848 KB Output is correct
4 Correct 11 ms 848 KB Output is correct
5 Correct 10 ms 768 KB Output is correct
6 Correct 11 ms 848 KB Output is correct
7 Incorrect 11 ms 764 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 11 ms 848 KB Output is correct
3 Correct 10 ms 848 KB Output is correct
4 Correct 11 ms 848 KB Output is correct
5 Correct 10 ms 768 KB Output is correct
6 Correct 11 ms 848 KB Output is correct
7 Incorrect 11 ms 764 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 8844 KB Output is correct
2 Correct 1594 ms 37916 KB Output is correct
3 Correct 1539 ms 37860 KB Output is correct
4 Correct 1562 ms 37980 KB Output is correct
5 Correct 1672 ms 37860 KB Output is correct
6 Correct 1734 ms 37856 KB Output is correct
7 Correct 1602 ms 37856 KB Output is correct
8 Correct 1531 ms 37860 KB Output is correct
9 Correct 1628 ms 37868 KB Output is correct
10 Correct 1566 ms 37860 KB Output is correct
11 Correct 1433 ms 37956 KB Output is correct
12 Correct 816 ms 37960 KB Output is correct
13 Correct 826 ms 37860 KB Output is correct
14 Correct 831 ms 37856 KB Output is correct
15 Correct 791 ms 37852 KB Output is correct
16 Correct 788 ms 37860 KB Output is correct
17 Correct 778 ms 37024 KB Output is correct
18 Correct 843 ms 38032 KB Output is correct
19 Correct 825 ms 37956 KB Output is correct
20 Correct 849 ms 37864 KB Output is correct
21 Correct 861 ms 37864 KB Output is correct
22 Correct 828 ms 37860 KB Output is correct
23 Correct 826 ms 37864 KB Output is correct
24 Correct 791 ms 37860 KB Output is correct
25 Correct 796 ms 37856 KB Output is correct
26 Correct 796 ms 37856 KB Output is correct
27 Correct 790 ms 37864 KB Output is correct
28 Correct 10 ms 768 KB Output is correct
29 Correct 11 ms 768 KB Output is correct
30 Correct 10 ms 772 KB Output is correct
31 Correct 11 ms 848 KB Output is correct
32 Correct 10 ms 768 KB Output is correct
33 Correct 5 ms 464 KB Output is correct
34 Correct 10 ms 784 KB Output is correct
35 Correct 10 ms 848 KB Output is correct
36 Correct 10 ms 848 KB Output is correct
37 Correct 11 ms 848 KB Output is correct
38 Correct 10 ms 848 KB Output is correct
39 Correct 13 ms 768 KB Output is correct
40 Correct 10 ms 768 KB Output is correct
41 Correct 10 ms 848 KB Output is correct
42 Correct 11 ms 768 KB Output is correct
43 Correct 10 ms 848 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 11 ms 848 KB Output is correct
3 Correct 10 ms 848 KB Output is correct
4 Correct 11 ms 848 KB Output is correct
5 Correct 10 ms 768 KB Output is correct
6 Correct 11 ms 848 KB Output is correct
7 Incorrect 11 ms 764 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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