Submission #708693

#	Time	Username	Problem	Language	Result	Execution time	Memory
708693		PixelCat	Two Antennas (JOI19_antennas)	C++14	100 / 100	724 ms	63148 KiB

antennas

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200020;
const int INF = 1e10;

#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
    const pii null = pii(INF, 0);
    pii a[MAXN << 2]; // {min, max}
    pii q[MAXN << 2]; // {min, max}
    int ans[MAXN << 2];
    
    pii merge(const pii &p1, const pii &p2) {
        return pii(min(p1.F, p2.F), max(p1.S, p2.S));
    }
    int eval(pii pa, pii pq) {
        int res = -1;
        if(pq.F < INF) {
            if(pa.F < INF) res = max(res, abs(pa.F - pq.F));
            if(pa.S > 0)   res = max(res, abs(pa.S - pq.F));
        }
        if(pq.S > 0) {
            if(pa.F < INF) res = max(res, abs(pa.F - pq.S));
            if(pa.S > 0)   res = max(res, abs(pa.S - pq.S));
        }
        return res;
    }
    
    void pull(int id) {
        a[id] = merge(a[L(id)], a[R(id)]);
        ans[id] = max(ans[L(id)], ans[R(id)]);
    }
    void addq(int id, pii pq) {
        ans[id] = max(ans[id], eval(a[id], pq));
        q[id] = merge(q[id], pq);
    }
    void push(int id) {
        if(q[id] != null) {
            addq(L(id), q[id]);
            addq(R(id), q[id]);
            q[id] = null;
        }
    }
    void init() {
        memset(ans, -1, sizeof(ans));
        For(i, 0, (MAXN << 2) - 1) {
            a[i] = q[i] = null;
        }
    }
    void upd(int id, int l, int r, int i, int x) {
        if(l == r) {
            if(x) a[id] = pii(x, x);
            else a[id] = null;
            return;
        }
        int m = (l + r) / 2;
        push(id);
        if(i <= m) upd(L(id), l, m, i, x);
        else       upd(R(id), m + 1, r, i, x);
        pull(id);
    }
    void updq(int id, int l, int r, int L, int R, int x) {
        if(l > R || r < L) return;
        if(l >= L && r <= R) {
            addq(id, pii(x, x));
            return;
        }
        int m = (l + r) / 2;
        push(id);
        if(L <= m) updq(L(id), l, m, L, R, x);
        if(R > m)  updq(R(id), m + 1, r, L, R, x);
        pull(id);
    }
    int qry(int id, int l, int r, int L, int R) {
        if(l > R || r < L) return -1;
        if(l >= L && r <= R) return ans[id];
        int res = -1;
        int m = (l + r) / 2;
        push(id);
        if(L <= m) res = max(res, qry(L(id), l, m, L, R));
        if(R > m)  res = max(res, qry(R(id), m + 1, r, L, R));
        pull(id);
        return res;
    }
} seg;

int h[MAXN];
int l[MAXN];
int r[MAXN];

vector<pii> vq[MAXN]; // {l, id}
int ans[MAXN];

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // NYA =^-w-^=
    int n; cin >> n;
    vector<pii> ev;
    For(i, 1, n) {
        cin >> h[i] >> l[i] >> r[i];
        ev.eb(i + l[i], i);
        ev.eb(i + r[i] + 1, -i);
    }
    sort(all(ev));
    reverse(all(ev));

    int q; cin >> q;
    For(i, 1, q) {
        int a, b; cin >> a >> b;
        vq[b].eb(a, i);
    }

    seg.init();
    For(i, 1, n) {
        while(sz(ev) && ev.back().F == i) {
            auto x = ev.back().S;
            seg.upd(0, 1, n, abs(x), (x < 0 ? 0 : h[x]));
            ev.pop_back();
        }
        seg.updq(0, 1, n, i - r[i], i - l[i], h[i]);
        for(auto &it:vq[i]) { // {l, id}
            ans[it.S] = seg.qry(0, 1, n, it.F, i);
        }
    }

    For(i, 1, q) cout << ans[i] << "\n";
    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65