Submission #579041

#	Time	Username	Problem	Language	Result	Execution time	Memory
579041		lcj	Two Antennas (JOI19_antennas)	C++17	22 / 100	467 ms	16292 KiB

antennas

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