Submission #471990

#	Time	Username	Problem	Language	Result	Execution time	Memory
471990		1bin	Two Antennas (JOI19_antennas)	C++14	100 / 100	1183 ms	59588 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e5 + 5;
const ll inf = 1e18;
ll n, h[NMAX], a[NMAX], b[NMAX], Q, ans[NMAX], l[NMAX], r[NMAX], base = 1, s, e;
vector<ll> p[NMAX], m[NMAX];
vector<pair<ll, ll>> query[NMAX];
vector<ll> c, d, lazy;

void init() {
	for (int i = 1; i <= n + 1; i++) {
		p[i].clear();
		m[i].clear();
	}
	for (int i = 1; i < base * 2; i++) c[i] = inf, d[i] = -inf, lazy[i] = -1;
	return;
}

void upd_lazy(ll idx) {
	if (lazy[idx] == -1) return;
	d[idx] = max(d[idx], lazy[idx] - c[idx]);
	if (idx < base) {
		lazy[idx * 2] = max(lazy[idx * 2], lazy[idx]);
		lazy[idx * 2 + 1] = max(lazy[idx * 2 + 1], lazy[idx]);
	}
	lazy[idx] = -1;
	return;
}

void updc(ll idx, ll nl, ll nr, ll k, ll v) {
	upd_lazy(idx);
	if (nl == nr) {
		c[idx] = v;
		return;
	}
	ll mid = (nl + nr) / 2;
	if (k <= mid) updc(idx * 2, nl, mid, k, v);
	else updc(idx * 2 + 1, mid + 1, nr, k, v);
	c[idx] = min(c[idx * 2], c[idx * 2 + 1]);
	return;
}

ll minc(ll l, ll r) {
	ll ret = inf;
	l += base; r += base;
	while (l <= r) {
		if (l & 1) ret = min(ret, c[l++]);
		if (!(r & 1)) ret = min(ret, c[r--]);
		l /= 2; r /= 2;
	}
	return ret;
}

void updd(ll idx, ll nl, ll nr, ll l, ll r, ll v) {
	upd_lazy(idx);
	if (nr < l || nl > r) return;
	if (nl >= l && nr <= r) {
		d[idx] = max(d[idx], v - c[idx]);
		if (nl != nr) {
			lazy[idx * 2] = max(lazy[idx * 2], v);
			lazy[idx * 2 + 1] = max(lazy[idx * 2 + 1], v);
		}
		return;
	}
	ll mid = (nl + nr) / 2;
	updd(idx * 2, nl, mid, l, r, v);
	updd(idx * 2 + 1, mid + 1, nr, l, r, v);
	d[idx] = max(d[idx * 2], d[idx * 2 + 1]);
	return;
}

ll mxd(ll idx, ll nl, ll nr, ll l, ll r) {
	upd_lazy(idx);
	if (nr < l || nl > r) return -inf;
	if (nl >= l && nr <= r) return d[idx];
	ll mid = (nl + nr) / 2;
	return max(mxd(idx * 2, nl, mid, l, r), mxd(idx * 2 + 1, mid + 1, nr, l, r));
}

void go() {
	init();
	for (int i = 1; i <= n; i++) {
		s = i + a[i];
		e = min(i + b[i] + 1, n + 1);
		if (s <= n) {
			p[s].emplace_back(i);
			m[e].emplace_back(i);
		}

		for (ll x : p[i]) updc(1, 0, base - 1, x, h[x]);
		for (ll x : m[i]) updc(1, 0, base - 1, x, inf);
		if (i > 1) {
			s = max(i - b[i], 1LL);
			e = i - a[i];
			if (e >= 1) updd(1, 0, base - 1, s, e, h[i]);
			for (auto& q : query[i])
				ans[q.second] = max(ans[q.second], mxd(1, 0, base - 1, q.first, i));
		}
	}
	return;
}

int main(void) {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;
	while (base < n + 1) base *= 2;
	c.resize(base * 2); d.resize(base * 2); lazy.resize(base * 2);

	for (int i = 1; i <= n; i++) cin >> h[i] >> a[i] >> b[i];
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		cin >> l[i] >> r[i];
		query[r[i]].emplace_back(l[i], i);
		ans[i] = -1;
	}
	go();

	reverse(h + 1, h + n + 1);
	reverse(a + 1, a + n + 1);
	reverse(b + 1, b + n + 1);
	for (int i = 1; i <= n; i++) query[i].clear();
	for (int i = 0; i < Q; i++) {
		l[i] = n + 1 - l[i];
		r[i] = n + 1 - r[i];
		swap(l[i], r[i]);
		query[r[i]].emplace_back(l[i], i);
	}
	go();

	for (int i = 0; i < Q; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

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