oj.uz

Submission #579041

# Submission time Handle Problem Language Result Execution time Memory
579041 2022-06-18T10:29:48 Z lcj Two Antennas (JOI19_antennas) C++17
22 / 100
 467 ms 16292 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

int left(int i) {return 2*i;}
int right(int i) {return 2*i+1;}
int parent(int i) {return i/2;}

struct Antenna {
    int h, a, b, i;
};

struct SegmentTreem {
    int n, nn;
    vector<int> st;
    SegmentTreem(int n) : n(n), nn(1 << (int)ceil(log2(n))), st(4*n, 1e9+1) {}
    int query(int l, int r, int a = 1, int b = -1, int i = 1) {
        if (b==-1) {b = nn;}
        if (l <= a && b <= r) {
            return st[i];
        }
        if (l > b || a > r) {return 1e9+1;}
        int mid = (a+b)/2;
        return min(query(l, r, a, mid, left(i)), query(l, r, mid+1, b, right(i)));
    }
    void update(int i, int v) {
        i = nn+i-1;
        st[i] = v;
        for (i = parent(i); i > 0; i = parent(i)) {
            st[i] = min(st[left(i)], st[right(i)]);
        }
    }
};
struct SegmentTreeM {
    int n, nn;
    vector<int> st;
    SegmentTreeM(int n) : n(n), nn(1 << (int)ceil(log2(n))), st(4*n, -1) {}
    int query(int l, int r, int a = 1, int b = -1, int i = 1) {
        if (b==-1) {b = nn;}
        if (l <= a && b <= r) {
            return st[i];
        }
        if (l > b || a > r) {return -1;}
        int mid = (a+b)/2;
        return max(query(l, r, a, mid, left(i)), query(l, r, mid+1, b, right(i)));
    }
    void update(int i, int v) {
        i = nn+i-1;
        st[i] = v;
        for (i = parent(i); i > 0; i = parent(i)) {
            st[i] = max(st[left(i)], st[right(i)]);
        }
    }
};

void solve() {
    int N;
    cin >> N;
    vector<Antenna> an(N+1);
    int h, a, b;
    for (int i = 1; i <= N; i++)
    {
        cin >> h >> a >> b;
        an[i] = Antenna {h, a, b, i};
    }
    int q;
    cin >> q;
    int l, r;
    for (int i = 0; i < q; i++)
    {
        cin >> l >> r;
    }
    SegmentTreem stm(N);
    SegmentTreeM stM(N);
    priority_queue<pii, vector<pii>, greater<pii>> pq_a;
    priority_queue<pii, vector<pii>, greater<pii>> pq_b;
    for (int i = 1; i < N+1; i++)
    {
        auto a = an[i];
        pq_a.push({a.i-a.b, a.i});
        pq_a.push({a.i+a.a, a.i});
        pq_b.push({a.i-a.a, a.i});
        pq_b.push({a.i+a.b, a.i});
    }
    int cmax = -1;
    for (int i = 1; i < N+1; i++)
    {
        while (!pq_a.empty() &&  pq_a.top().first <= i)
        {
            auto cur = pq_a.top();pq_a.pop();
            stm.update(cur.second, an[cur.second].h);
            stM.update(cur.second, an[cur.second].h);
        }
        while (!pq_b.empty() && pq_b.top().first < i)
        {
            auto tod = pq_b.top();pq_b.pop();
            stm.update(tod.second, 1e9+1);
            stM.update(tod.second, -1);
        }
        auto cur = an[i];
        int m1 = 1e9+1;int m2 = 1e9+1;
        int M1 = -1;int M2 = -1;
        if (cur.i-cur.a >= 1) {
            m1 = stm.query(max(1, cur.i-cur.b), cur.i-cur.a);
            M1 = stM.query(max(1, cur.i-cur.b), cur.i-cur.a);
        }
        if (cur.i+cur.a <= N) {
            m2 = stm.query(cur.i+cur.a, min(N, cur.i+cur.b));
            M2 = stM.query(cur.i+cur.a, min(N, cur.i+cur.b));
        }
        if (m1 != 1e9+1) {
            cmax = max(cmax, max(abs(m1-cur.h), abs(M1-cur.h)));
        }
        if (m2 != 1e9+1) {
            cmax = max(cmax, max(abs(m2-cur.h), abs(M2-cur.h)));
        }
    }
    cout << cmax << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    solve();
    return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 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 212 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 411 ms 15144 KB Output is correct
2 Correct 395 ms 16204 KB Output is correct
3 Correct 311 ms 13248 KB Output is correct
4 Correct 378 ms 16200 KB Output is correct
5 Correct 155 ms 7892 KB Output is correct
6 Correct 467 ms 16212 KB Output is correct
7 Correct 329 ms 14788 KB Output is correct
8 Correct 424 ms 16224 KB Output is correct
9 Correct 50 ms 3016 KB Output is correct
10 Correct 429 ms 16212 KB Output is correct
11 Correct 240 ms 10328 KB Output is correct
12 Correct 435 ms 16216 KB Output is correct
13 Correct 288 ms 16200 KB Output is correct
14 Correct 268 ms 16100 KB Output is correct
15 Correct 250 ms 16292 KB Output is correct
16 Correct 258 ms 16100 KB Output is correct
17 Correct 276 ms 16104 KB Output is correct
18 Correct 274 ms 16208 KB Output is correct
19 Correct 262 ms 16104 KB Output is correct
20 Correct 261 ms 16100 KB Output is correct
21 Correct 273 ms 16208 KB Output is correct
22 Correct 288 ms 16204 KB Output is correct
23 Correct 275 ms 16212 KB Output is correct
24 Correct 248 ms 16292 KB Output is correct

Subtask #4
0 / 65.0

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