Submission #476179

#	Time	Username	Problem	Language	Result	Execution time	Memory
476179		flappybird	Two Antennas (JOI19_antennas)	C++14	100 / 100	1357 ms	70652 KiB

antennas

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAX 200100
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
struct node {
	ll mxval, mnval;
	ll ans;
	node() {
		mxval = mnval = ans = -1;
	}
};
node operator+(const node& n1, const node& n2) {
	node ret;
	ret.mnval = n1.mnval == -1 ? n2.mnval : (n2.mnval == -1 ? n1.mnval : min(n1.mnval, n2.mnval));
	ret.mxval = max(n1.mxval, n2.mxval);
	ret.ans = max(n1.ans, n2.ans);
	return ret;
}
struct segtree {
	ll N, s;
	vector<node> tree;
	vector<ll> l, r;
	vector<ll> lmx, lmn; //lazy max min
	void init(ll x = 1) {
		if (x >= s) {
			l[x] = r[x] = x - s + 1;
			return;
		}
		init(x * 2);
		init(x * 2 + 1);
		l[x] = l[x * 2];
		r[x] = r[x * 2 + 1];
	}
	segtree() {}
	segtree(ll N) {
		segtree::N = N;
		s = 1LL << (ll)ceil(log2(N));
		tree.resize(2 * s + 1);
		l.resize(2 * s + 1);
		r.resize(2 * s + 1);
		lmx.resize(2 * s + 1, -1);
		lmn.resize(2 * s + 1, -1);
		init();
	}
	void prop(ll loc) {
		if (loc >= s) {
			lmx[loc] = lmn[loc] = -1;
			return;
		}
		lmx[loc * 2] = max(lmx[loc * 2], lmx[loc]);
		lmx[loc * 2 + 1] = max(lmx[loc * 2 + 1], lmx[loc]);
		if (lmx[loc] != -1) lmn[loc * 2] = min(lmn[loc * 2], lmn[loc]);
		if (lmx[loc] != -1) lmn[loc * 2 + 1] = min(lmn[loc * 2 + 1], lmn[loc]);
		if (lmn[loc * 2] == -1) lmn[loc * 2] = lmn[loc];
		if (lmn[loc * 2 + 1] == -1) lmn[loc * 2 + 1] = lmn[loc];
		ll res = -1;
		if (tree[loc * 2].mxval != -1 && lmx[loc * 2] != -1) res = max(res, abs(tree[loc * 2].mxval - lmx[loc * 2]));
		if (tree[loc * 2].mxval != -1 && lmn[loc * 2] != -1) res = max(res, abs(tree[loc * 2].mxval - lmn[loc * 2]));
		if (tree[loc * 2].mnval != -1 && lmx[loc * 2] != -1) res = max(res, abs(tree[loc * 2].mnval - lmx[loc * 2]));
		if (tree[loc * 2].mnval != -1 && lmn[loc * 2] != -1) res = max(res, abs(tree[loc * 2].mnval - lmn[loc * 2]));
		tree[loc * 2].ans = max(tree[loc * 2].ans, res);
		res = -1;
		if (tree[loc * 2 + 1].mxval != -1 && lmx[loc * 2 + 1] != -1) res = max(res, abs(tree[loc * 2 + 1].mxval - lmx[loc * 2 + 1]));
		if (tree[loc * 2 + 1].mxval != -1 && lmn[loc * 2 + 1] != -1) res = max(res, abs(tree[loc * 2 + 1].mxval - lmn[loc * 2 + 1]));
		if (tree[loc * 2 + 1].mnval != -1 && lmx[loc * 2 + 1] != -1) res = max(res, abs(tree[loc * 2 + 1].mnval - lmx[loc * 2 + 1]));
		if (tree[loc * 2 + 1].mnval != -1 && lmn[loc * 2 + 1] != -1) res = max(res, abs(tree[loc * 2 + 1].mnval - lmn[loc * 2 + 1]));
		tree[loc * 2 + 1].ans = max(tree[loc * 2 + 1].ans, res);
		lmx[loc] = lmn[loc] = -1;
	}
	void update(ll low, ll high, ll h, ll loc = 1) {
		prop(loc);
		if (high == 0) return;
		low = max(1LL, low);
		if (tree[loc].mnval == -1) return;
		prop(loc);
		if (low == l[loc] && high == r[loc]) {
			lmx[loc] = max(lmx[loc], h);
			lmn[loc] = min(lmn[loc], h);
			if (lmn[loc] == -1) lmn[loc] = h;
			ll res = 0;
			if (tree[loc].mnval != -1) res = max(res, abs(h - tree[loc].mnval));
			if (tree[loc].mxval != -1) res = max(res, abs(h - tree[loc].mxval));
			tree[loc].ans = max(tree[loc].ans, res);
			return;
		}
		if (high <= r[loc * 2]) update(low, high, h, loc * 2);
		else if (low >= l[loc * 2 + 1]) update(low, high, h, loc * 2 + 1);
		else update(low, r[loc * 2], h, loc * 2), update(l[loc * 2 + 1], high, h, loc * 2 + 1);
		tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
	}
	void togle(ll x, ll v, ll loc = 1) {
		prop(loc);
		if (l[loc] == r[loc]) {
			tree[loc].mnval = tree[loc].mxval = v;
			return;
		}
		if (x <= r[loc * 2]) togle(x, v, loc * 2);
		else togle(x, v, loc * 2 + 1);
		tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
	}
	ll query(ll low, ll high, ll loc = 1) {
		prop(loc);
		if (low == l[loc] && high == r[loc]) return tree[loc].ans;
		if (high <= r[loc * 2]) return query(low, high, loc * 2);
		if (low >= l[loc * 2 + 1]) return query(low, high, loc * 2 + 1);
		return max(query(low, r[loc * 2], loc * 2), query(l[loc * 2 + 1], high, loc * 2 + 1));
	}
};
struct query {
	ll l, r;
	ll ind;
	query() {}
	query(ll l, ll r, ll ind) :l(l), r(r), ind(ind) {}
};
vector<query> qarr[MAX];
vector<ll> on[MAX], off[MAX];
ll ans[MAX];
ll H[MAX];
ll l[MAX], r[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll N;
	cin >> N;
	ll i;
	ll a, b;
	for (i = 1; i <= N; i++) {
		cin >> H[i] >> a >> b;
		l[i] = max(i - b, 0LL);
		r[i] = max(i - a, 0LL);
		on[min(N + 1, i + a)].push_back(i);
		off[min(N + 1, i + b + 1)].push_back(i);
	}
	ll Q;
	cin >> Q;
	for (i = 1; i <= Q; i++) {
		cin >> a >> b;
		qarr[b].push_back(query(a, b, i));
	}
	segtree seg(N);
	for (i = 1; i <= N; i++) {
		for (auto x : on[i]) seg.togle(x, H[x]);
		for (auto x : off[i]) seg.togle(x, -1);
		seg.update(l[i], r[i], H[i]);
		for (auto q : qarr[i]) ans[q.ind] = seg.query(q.l, i);
	}
	for (i = 1; i <= Q; i++) cout << ans[i] << ln;
}

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