oj.uz

Submission #868929

# Submission time Handle Problem Language Result Execution time Memory
868929 2023-11-02T12:50:50 Z rockstar Two Antennas (JOI19_antennas) C++17
22 / 100
 165 ms 36544 KB 
// #pragma GCC optimize("O3,unroll-loops,inline,no-stack-protector")
// #pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2,fma,bmi2,abm,popcnt,mmx,tune=native")

#include <bits/stdc++.h>

using namespace std;

#define trace(x) cerr << #x << ": " << (x) << endl;
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

using ll = long long;

#define int ll

constexpr int INF = numeric_limits<int>::max() / 2;

struct node {
    int h, a, b;
};

struct segment_tree {
    vector<pair<int, int>> tree;
    int n;

    segment_tree(int n_) {
        n = n_;
        tree.resize(4 * n, { INF, -INF });
    }

    void upd(int v, int tl, int tr, int i, int x1, int x2) {
        if (tl == tr)
            return void(tree[v] = { x1, x2 });
        int tm = (tl + tr) / 2;
        if (i <= tm)
            upd(v * 2, tl, tm, i, x1, x2);
        else
            upd(v * 2 + 1, tm + 1, tr, i, x1, x2);
        tree[v] = { min(tree[v * 2].first, tree[v * 2 + 1].first), max(tree[v * 2].second, tree[v * 2 + 1].second) };
    }

    pair<int, int> get(int v, int tl, int tr, int l, int r) {
        if (r < tl || tr < l)
            return { INF, -INF };
        if (l <= tl && tr <= r)
            return tree[v];
        int tm = (tl + tr) / 2;
        auto ls = get(v * 2, tl, tm, l, r), rs = get(v * 2 + 1, tm + 1, tr, l, r);
        return { min(ls.first, rs.first), max(ls.second, rs.second) };
    }

    pair<int, int> get(int l, int r) {
        return get(1, 0, n - 1, l, r);
    }

    void upd(int i, int x1, int x2) {
        upd(1, 0, n - 1, i, x1, x2);
    }
};

struct que {
    int x, ind, type;
};

bool operator<(que a, que b) {
    if (a.x != b.x)
        return a.x < b.x;
    return a.type > b.type;
}

void solve() {
    int n;
    cin >> n;
    vector<node> v(n);
    for (auto& i : v)
        cin >> i.h >> i.a >> i.b;
    int q, l, r;
    cin >> q >> l >> r;
    segment_tree tr(n);
    vector<que> qq;
    for (int i = 0; i < n; ++i) {
        if (i + v[i].a < n)
            qq.push_back({ i + v[i].a, i, 2 });
        qq.push_back({ min(i + v[i].b, n - 1), i, 0 });
        qq.push_back({ i, i, 1 });
    }
    sort(all(qq));
    int ans = -1;
    for (int i = 0; i < qq.size(); ++i) {
        if (qq[i].type == 0)
            tr.upd(qq[i].ind, INF, -INF);
        if (qq[i].type == 2)
            tr.upd(qq[i].ind, v[qq[i].ind].h, v[qq[i].ind].h);
        if (qq[i].type == 1) {
            auto res = tr.get(qq[i].ind - v[qq[i].ind].b, qq[i].ind - v[qq[i].ind].a);
            if (res.first != INF)
                ans = max(ans, abs(v[qq[i].ind].h - res.first));
            if (res.second != -INF)
                ans = max(ans, abs(v[qq[i].ind].h - res.second));
        }
    }
    cout << ans;
}

signed main() {
#ifdef LOCAL
    freopen("input.in", "r", stdin);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
#ifdef LOCAL
    cerr << '\n' << "time = " << clock() * 1.0 / CLOCKS_PER_SEC << '\n';
#endif
    return 0;
}

Compilation message

antennas.cpp: In function 'void solve()':
antennas.cpp:89:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<que>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < qq.size(); ++i) {
      |                     ~~^~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 34428 KB Output is correct
2 Correct 146 ms 35004 KB Output is correct
3 Correct 109 ms 29328 KB Output is correct
4 Correct 165 ms 35516 KB Output is correct
5 Correct 68 ms 17092 KB Output is correct
6 Correct 161 ms 36028 KB Output is correct
7 Correct 150 ms 32956 KB Output is correct
8 Correct 143 ms 36544 KB Output is correct
9 Correct 22 ms 6860 KB Output is correct
10 Correct 157 ms 34964 KB Output is correct
11 Correct 88 ms 26816 KB Output is correct
12 Correct 147 ms 35184 KB Output is correct
13 Correct 112 ms 35776 KB Output is correct
14 Correct 114 ms 36284 KB Output is correct
15 Correct 110 ms 36288 KB Output is correct
16 Correct 104 ms 35804 KB Output is correct
17 Correct 113 ms 35264 KB Output is correct
18 Correct 120 ms 34544 KB Output is correct
19 Correct 110 ms 34676 KB Output is correct
20 Correct 109 ms 36352 KB Output is correct
21 Correct 110 ms 35440 KB Output is correct
22 Correct 117 ms 35200 KB Output is correct
23 Correct 109 ms 34548 KB Output is correct
24 Correct 103 ms 34492 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -