oj.uz

Submission #717512

# Submission time Handle Problem Language Result Execution time Memory
717512 2023-04-02T03:54:35 Z walterw Two Antennas (JOI19_antennas) C++17
22 / 100
 2200 ms 58296 KB 
#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

#define int ll

int H[200005], A[200005], B[200005];

struct event {
    int time, idx, height; bool add;

    bool operator<(event o) const {
        if (time == o.time) {
            if (!add) return true;
            return false;
        }
        return time < o.time;
    }
};

vector<event> events;

pair<int, int> vals[4 * 200005];
int ans[4 * 200005];
pair<int, int> qs[4 * 200005];
const pair<int, int> null = {1e16, 0};

void build() {
    fill(ans, ans+ 4 * 200005, -1);
    for (int i = 1; i < 4 * 200005; i++) {
        vals[i] = qs[i] = null;
    }
}

pair<int, int> comb(pair<int, int> a, pair<int, int> b) {
    return {min(a.first, b.first), max(a.second, b.second)};
}

int eval(pair<int, int> vals, pair<int, int> qs) {
    int res = - 1;

    if (qs.first < (ll) 1e16) {
        if (vals.first < (ll) 1e16) res = max(res, abs(qs.first - vals.first));
        if (vals.second > 0) res = max(res, abs(qs.first - vals.second));
    }
    if (qs.second > 0) {
        if (vals.first < (ll) 1e16) res = max(res, abs(qs.second - vals.first));
        if (vals.second > 0) res = max(res, abs(qs.second - vals.second));
    }

    return res;
}

void push(int x) {
    if (qs[x] != null) {
        ans[2 * x] = max(ans[2 * x], eval(vals[2 * x], qs[x]));
        qs[2 * x] = comb(qs[2 * x], qs[x]);

        ans[2 * x + 1] = max(ans[2 * x + 1], eval(vals[2 * x + 1], qs[x]));
        qs[2 * x + 1] = comb(qs[2 * x + 1], qs[x]);

        qs[x] = null;
    }
}

void update(int x, int l, int r, int idx, int h) {
    if (l == r) {
        if (h) vals[x] = {h, h};
        else vals[x] = {1e16, 0};
        return;
    }

    push(x);
    int mid = (l + r) / 2;
    if (idx <= mid) update(2 * x, l, mid, idx, h);
    else update(2 * x + 1, mid + 1, r, idx, h);

    vals[x] = comb(vals[2 * x], vals[2 * x + 1]);
    ans[x] = max(ans[2 * x], ans[2 * x + 1]);
}

void updatequery(int x, int l, int r, int ql, int qr, int curh) {
    if (ql <= l && r <= qr) {
        // fully within
        ans[x] = max(ans[x], eval(vals[x], {curh, curh}));
        qs[x] = comb(qs[x], {curh, curh});
        return;
    }

    if (l > qr || ql > r) return;

    int mid = (l + r) / 2;
    push(x);

    updatequery(2 * x, l, mid, ql, qr , curh);
    updatequery(2 * x + 1, mid + 1, r, ql, qr, curh);

    vals[x] = comb(vals[2 * x], vals[2 * x + 1]);
    ans[x] = max(ans[2 * x], ans[2 * x + 1]);
}

int query(int x, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return ans[x];
    if (l > qr || ql > r) return -1;

    int mid = (l + r) / 2;
    push(x);

    return max(query(2 * x, l, mid, ql, qr), query(2 * x + 1, mid + 1, r, ql, qr));
}


vector<pair<int, int>> queries[200005];
int toprint[200005];

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> H[i] >> A[i] >> B[i];
    }

    int q; cin >> q;
    for (int i = 1; i <= q; i++) {
        int a, b; cin >> a >> b;
        queries[b].emplace_back(a, i);
    }

    for (int i = 1; i <= n; i++) {
        events.push_back({i + A[i], i,  H[i], true});
        events.push_back({i + B[i] + 1, i, H[i], false});
    }

    sort(events.begin(), events.end());
    int idx = 0;

    build();

    for (int i = 1; i <= n; i++) {
        while (idx < events.size() && events[idx].time == i) {
            if (events[idx].add) {
                update(1, 1, n, events[idx].idx, events[idx].height);
            } else {
                update(1, 1, n, events[idx].idx, 0);
            }

            idx++;
        }


        updatequery(1, 1, n, max((ll) 1, i - B[i]), max((ll) 1, i - A[i]), H[i]);

        for (auto [l, id] : queries[i]) {
            toprint[id] = query(1, 1, n, l, i);
        }
    }

    for (int i = 1; i <= q; i++) {
        cout << toprint[i] << "\n";
    }

}

Compilation message

antennas.cpp: In function 'int32_t main()':
antennas.cpp:170:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |         while (idx < events.size() && events[idx].time == i) {
      |                ~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 36308 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 331 ms 51888 KB Output is correct
2 Correct 350 ms 58100 KB Output is correct
3 Correct 304 ms 51636 KB Output is correct
4 Correct 351 ms 58296 KB Output is correct
5 Correct 161 ms 46400 KB Output is correct
6 Correct 354 ms 58136 KB Output is correct
7 Correct 295 ms 55216 KB Output is correct
8 Correct 349 ms 58272 KB Output is correct
9 Correct 58 ms 39840 KB Output is correct
10 Correct 355 ms 58152 KB Output is correct
11 Correct 199 ms 49952 KB Output is correct
12 Correct 367 ms 58132 KB Output is correct
13 Correct 1621 ms 58044 KB Output is correct
14 Correct 829 ms 58044 KB Output is correct
15 Correct 449 ms 58032 KB Output is correct
16 Correct 428 ms 58044 KB Output is correct
17 Correct 1572 ms 58036 KB Output is correct
18 Correct 435 ms 58048 KB Output is correct
19 Correct 1687 ms 58060 KB Output is correct
20 Correct 973 ms 58032 KB Output is correct
21 Correct 2200 ms 58020 KB Output is correct
22 Correct 1210 ms 58040 KB Output is correct
23 Correct 525 ms 58012 KB Output is correct
24 Correct 710 ms 58044 KB Output is correct

Subtask #4
0 / 65.0

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