Submission #708677

#	Time	Username	Problem	Language	Result	Execution time	Memory
708677		PixelCat	Two Antennas (JOI19_antennas)	C++14	22 / 100	320 ms	24176 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 merge(const pii &p1, const pii &p2) {
        return pii(min(p1.F, p2.F), max(p1.S, p2.S));
    }
    
    void pull(int id) {
        a[id] = merge(a[L(id)], a[R(id)]);
    }
    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;
        if(i <= m) upd(L(id), l, m, i, x);
        else       upd(R(id), m + 1, r, i, x);
        pull(id);
    }
    pii qry(int id, int l, int r, int L, int R) {
        if(l > R || r < L) return null;
        if(l >= L && r <= R) return a[id];
        pii res = null;
        int m = (l + r) / 2;
        if(L <= m) res = merge(res, qry(L(id), l, m, L, R));
        if(R > m)  res = merge(res, qry(R(id), m + 1, r, L, R));
        return res;
    }
} seg;

int h[MAXN];
int l[MAXN];
int r[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 ans = -1;
    For(i, 1, n) seg.upd(0, 1, n, i, 0);
    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();
        }
        auto res = seg.qry(0, 1, n, i - r[i], i - l[i]);
        if(res.F < INF) ans = max(ans, abs(h[i] - res.F));
        if(res.S > 0) ans = max(ans, abs(h[i] - res.S));
    }
    cout << ans << "\n";
    return 0;
}

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