Submission #868929

#	Time	Username	Problem	Language	Result	Execution time	Memory
868929		rockstar	Two Antennas (JOI19_antennas)	C++17	22 / 100	165 ms	36544 KiB

antennas

// #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 (stderr)

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
• Subtask 2: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65