oj.uz

Submission #1074458

# Submission time Handle Problem Language Result Execution time Memory
1074458 2024-08-25T10:37:03 Z shmax Radio Towers (IOI22_towers) C++17
17 / 100
 761 ms 43864 KB 
#include "towers.h"
#include <bits/stdc++.h>

using namespace std;
#define bit(x, i) ((x >> i) & 1)
#define inf 2000'000'000LL
template<typename T>
using vec = vector<T>;


template<typename it>
struct SparseTable {

    using T = typename remove_reference<decltype(*declval<it>())>::type;
    vector<vector<T>> t;
    function<T(T, T)> f;
    vector<int> log;

    SparseTable() = default;

    SparseTable(it first, it last, function<T(T, T)> op) : t(1), f(op) {
        int n = distance(first, last);
        t.assign(32 - __builtin_clz(n), vector<T>(n));
        t[0].assign(first, last);
        log.resize(n + 1);
        for (int i = 2; i <= n; i++)
            log[i] = log[i / 2] + 1;

        for (int i = 1; i < t.size(); i++)
            for (int j = 0; j < n - (1 << i) + 1; j++)
                t[i][j] = f(t[i - 1][j], t[i - 1][j + (1 << (i - 1))]);
    }

    T get(int l, int r) {
        int h = log[r - l + 1];
        return f(t[h][l], t[h][r - (1 << h) + 1]);
    }
};

struct node {
    int l, r;
    int sum;
};
vec<node> nodes;

void fetch(int x) {
    int sm = 0;
    if (nodes[x].l != -1) {
        sm += nodes[nodes[x].l].sum;
    }
    if (nodes[x].r != -1) {
        sm += nodes[nodes[x].r].sum;
    }
    nodes[x].sum = sm;
}

int new_node() {
    nodes.push_back({-1, -1, 0});
    return nodes.size() - 1;
}

vec<int> roots;

int build(int tl, int tr) {
    if (tl == tr) {
        int id = new_node();
        nodes[id].sum = 0;
        return id;
    }
    int id = new_node();
    int tm = (tl + tr) / 2;
    int l = build(tl, tm);
    int r = build(tm + 1, tr);
    nodes[id].l = l;
    nodes[id].r = r;
    fetch(id);
    return id;
}

int get(int v, int tl, int tr, int l, int r) {
    if (tl == l and tr == r) {
        return nodes[v].sum;
    }
    int tm = (tl + tr) / 2;
    if (r <= tm) {
        return get(nodes[v].l, tl, tm, l, r);
    }
    if (l > tm) {
        return get(nodes[v].r, tm + 1, tr, l, r);
    }
    return get(nodes[v].l, tl, tm, l, tm) + get(nodes[v].r, tm + 1, tr, tm + 1, r);
}

int update(int v, int tl, int tr, int pos, int x) {
    if (tl == tr) {
        int id = new_node();
        nodes[id].sum = x;
        return id;
    }
    int tm = (tl + tr) / 2;
    int id = new_node();
    if (pos <= tm) {
        int tid = update(nodes[v].l, tl, tm, pos, x);
        nodes[id].l = tid;
        nodes[id].r = nodes[v].r;
    } else {
        int tid = update(nodes[v].r, tm + 1, tr, pos, x);
        nodes[id].l = nodes[v].l;
        nodes[id].r = tid;
    }
    fetch(id);
    return id;
}

vec<int> h;
int n;
vec<pair<int, int>> deltas;

void init(int N, std::vector<int> H) {
    n = N;
    h = H;
    SparseTable stmin(h.begin(), h.end(), [](int a, int b) { return min(a, b); });
    SparseTable stmax(h.begin(), h.end(), [](int a, int b) { return max(a, b); });
    for (int i = 0; i < n; i++) {
        int h1 = inf;
        if (i != 0) {
            if (stmin.get(0, i - 1) < h[i]) {
                int tl = 0;
                int tr = i - 1;
                while (tl != tr) {
                    int tm = (tl + tr + 1) / 2;
                    if (stmin.get(tm, i - 1) < h[i]) {
                        tl = tm;
                    } else {
                        tr = tm - 1;
                    }
                }
                h1 = stmax.get(tl, i - 1);
            }
        }
        int h2 = inf;
        if (i != n - 1) {
            if (stmin.get(i + 1, n - 1) < h[i]) {
                int tl = i + 1;
                int tr = n - 1;
                while (tl != tr) {
                    int tm = (tl + tr) / 2;
                    if (stmin.get(i + 1, tm) < h[i]) {
                        tr = tm;
                    } else {
                        tl = tm + 1;
                    }
                }
                h2 = stmax.get(i + 1, tr);
            }
        }
        int max_delta = min(h1, h2) - h[i];
        deltas.push_back({max_delta, i});
    }

    sort(deltas.rbegin(), deltas.rend());
    int t = build(0, n - 1);
    roots.push_back(t);
    for (auto [d, i]: deltas) {
        t = update(roots.back(), 0, n - 1, i, 1);
        roots.push_back(t);
    }
}

int max_towers(int L, int R, int D) {
    int tl = 0;
    int tr = n - 1;
    while (tl != tr) {
        int tm = (tl + tr + 1) / 2;
        if (deltas[tm].first >= D) {
            tl = tm;
        } else {
            tr = tm - 1;
        }
    }
    if (deltas[0].first < D)
        tl = -1;
    int vr = roots[tl + 1];
    int ans = get(vr, 0, n - 1, L, R);
    return ans;
}

Compilation message

towers.cpp: In instantiation of 'SparseTable<it>::SparseTable(it, it, std::function<typename std::remove_reference<decltype (* declval<it>())>::type(typename std::remove_reference<decltype (* declval<it>())>::type, typename std::remove_reference<decltype (* declval<it>())>::type)>) [with it = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; typename std::remove_reference<decltype (* declval<it>())>::type = int]':
towers.cpp:122:81:   required from here
towers.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int>, std::allocator<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int i = 1; i < t.size(); i++)
      |                         ~~^~~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 1120 KB Output is correct
3 Correct 2 ms 1120 KB Output is correct
4 Correct 3 ms 1120 KB Output is correct
5 Correct 2 ms 1120 KB Output is correct
6 Correct 2 ms 1120 KB Output is correct
7 Incorrect 3 ms 1120 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 2 ms 600 KB Output is correct
2 Correct 2 ms 1120 KB Output is correct
3 Correct 2 ms 1120 KB Output is correct
4 Correct 3 ms 1120 KB Output is correct
5 Correct 2 ms 1120 KB Output is correct
6 Correct 2 ms 1120 KB Output is correct
7 Incorrect 3 ms 1120 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 653 ms 41648 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 211 ms 10308 KB Output is correct
2 Correct 716 ms 41908 KB Output is correct
3 Correct 692 ms 43068 KB Output is correct
4 Correct 644 ms 42164 KB Output is correct
5 Correct 650 ms 42164 KB Output is correct
6 Correct 686 ms 42488 KB Output is correct
7 Correct 750 ms 42588 KB Output is correct
8 Correct 675 ms 42324 KB Output is correct
9 Correct 717 ms 41868 KB Output is correct
10 Correct 668 ms 42548 KB Output is correct
11 Correct 761 ms 41912 KB Output is correct
12 Correct 80 ms 42592 KB Output is correct
13 Correct 77 ms 42804 KB Output is correct
14 Correct 83 ms 43704 KB Output is correct
15 Correct 76 ms 42440 KB Output is correct
16 Correct 83 ms 42028 KB Output is correct
17 Correct 79 ms 42280 KB Output is correct
18 Correct 83 ms 43864 KB Output is correct
19 Correct 85 ms 43444 KB Output is correct
20 Correct 77 ms 43076 KB Output is correct
21 Correct 80 ms 43188 KB Output is correct
22 Correct 77 ms 43616 KB Output is correct
23 Correct 80 ms 43776 KB Output is correct
24 Correct 72 ms 43188 KB Output is correct
25 Correct 74 ms 42164 KB Output is correct
26 Correct 94 ms 42048 KB Output is correct
27 Correct 70 ms 41924 KB Output is correct
28 Correct 1 ms 1120 KB Output is correct
29 Correct 2 ms 1120 KB Output is correct
30 Correct 1 ms 1120 KB Output is correct
31 Correct 2 ms 1120 KB Output is correct
32 Correct 1 ms 1120 KB Output is correct
33 Correct 1 ms 800 KB Output is correct
34 Correct 3 ms 1120 KB Output is correct
35 Correct 1 ms 1120 KB Output is correct
36 Correct 1 ms 1120 KB Output is correct
37 Correct 1 ms 1120 KB Output is correct
38 Correct 2 ms 1120 KB Output is correct
39 Correct 2 ms 1120 KB Output is correct
40 Correct 1 ms 1120 KB Output is correct
41 Correct 1 ms 1120 KB Output is correct
42 Correct 2 ms 1120 KB Output is correct
43 Correct 1 ms 1120 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 1120 KB Output is correct
3 Correct 2 ms 1120 KB Output is correct
4 Correct 3 ms 1120 KB Output is correct
5 Correct 2 ms 1120 KB Output is correct
6 Correct 2 ms 1120 KB Output is correct
7 Incorrect 3 ms 1120 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 361 ms 36076 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -