oj.uz

Submission #717514

# Submission time Handle Problem Language Result Execution time Memory
717514 2023-04-02T04:00:01 Z walterw Two Antennas (JOI19_antennas) C++17
22 / 100
 2049 ms 53660 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] = null;
        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);

    int ans1 = query(2 * x, l, mid, ql, qr);
    int ans2 = query(2 * x + 1, mid + 1, r, ql, qr);

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


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:176: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]
  176 |         while (idx < events.size() && events[idx].time == i) {
      |                ~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 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 15 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 309 ms 51948 KB Output is correct
2 Correct 357 ms 53656 KB Output is correct
3 Correct 234 ms 48520 KB Output is correct
4 Correct 364 ms 53600 KB Output is correct
5 Correct 143 ms 44440 KB Output is correct
6 Correct 343 ms 53656 KB Output is correct
7 Correct 297 ms 51332 KB Output is correct
8 Correct 339 ms 53592 KB Output is correct
9 Correct 53 ms 39188 KB Output is correct
10 Correct 344 ms 53612 KB Output is correct
11 Correct 196 ms 47152 KB Output is correct
12 Correct 355 ms 53656 KB Output is correct
13 Correct 1508 ms 53612 KB Output is correct
14 Correct 801 ms 53612 KB Output is correct
15 Correct 430 ms 53660 KB Output is correct
16 Correct 411 ms 53580 KB Output is correct
17 Correct 1499 ms 53608 KB Output is correct
18 Correct 398 ms 53656 KB Output is correct
19 Correct 1672 ms 53652 KB Output is correct
20 Correct 1045 ms 53572 KB Output is correct
21 Correct 2049 ms 53660 KB Output is correct
22 Correct 1170 ms 53656 KB Output is correct
23 Correct 499 ms 53656 KB Output is correct
24 Correct 591 ms 53660 KB Output is correct

Subtask #4
0 / 65.0

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