Submission #464472

#	Time	Username	Problem	Language	Result	Execution time	Memory
464472		pavement	Two Antennas (JOI19_antennas)	C++17	0 / 100	495 ms	60172 KiB

antennas

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, Q, H[200005], A[200005], B[200005], T[200005], out[200005];
bool act[200005];
vector<int> toact[200005], todeact[200005];
vector<ii> qu[200005];

struct node {
	node *left, *right;
	int S, E, val, mi, mx, mip, mxp;
	node(int _s, int _e) : S(_s), E(_e), val(-1), mi(1e16), mx(-1e16), mip(1e16), mxp(-1e16) {
		if (S == E) return;
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
	}
	void prop() {
		if (S == E || mip == 1e16) return;
		left->mip = min(left->mip, mip);
		left->mxp = max(left->mxp, mxp);
		if (left->mi != 1e16) left->val = max({left->val, llabs(left->mi - left->mxp), llabs(left->mx - left->mip)});
		right->mip = min(right->mip, mip);
		right->mxp = max(right->mxp, mxp);
		if (right->mi != 1e16) right->val = max({right->val, llabs(right->mi - right->mxp), llabs(right->mx - right->mip)});
		mip = 1e16;
		mxp = -1e16;
	}
	void upd(int l, int r, int v) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			mxp = max(mxp, v);
			mip = min(mip, v);
			if (mi != 1e16) val = max({val, llabs(mxp - mi), llabs(mip - mx)});
			return;
		}
		prop();
		left->upd(l, r, v);
		right->upd(l, r, v);
		val = max(left->val, right->val);
	}
	void act(int p) {
		if (S == E) {
			mi = mx = H[p];
			return;
		}
		prop();
		int M = (S + E) >> 1;
		if (p <= M) left->act(p);
		else right->act(p);
		mi = min(left->mi, right->mi);
		mx = max(left->mx, right->mx);
	}
	void deact(int p) {
		if (S == E) {
			mi = 1e16;
			mx = -1e16;
			return;
		}
		prop();
		int M = (S + E) >> 1;
		if (p <= M) left->deact(p);
		else right->deact(p);
		mi = min(left->mi, right->mi);
		mx = max(left->mx, right->mx);
	}
	int qry(int l, int r) {
		if (l > E || r < S) return -1;
		if (l <= S && E <= r) return val;
		prop();
		return max(left->qry(l, r), right->qry(l, r));
	}
} *root;

main() {
	memset(T, -1, sizeof T);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	root = new node(1, N);
	for (int i = 1; i <= N; i++) cin >> H[i] >> A[i] >> B[i];
	cin >> Q;
	for (int i = 1, L, R; i <= Q; i++) {
		cin >> L >> R;
		qu[R].eb(L, i);
	}
	for (int i = 1; i <= N; i++) {
		for (auto j : toact[i]) root->act(j);
		for (auto j : todeact[i]) root->deact(j);
		root->upd(max(1ll, i - B[i]), max(1ll, i - A[i]), H[i]);
		for (auto u : qu[i]) out[u.second] = root->qry(u.first, i);
		if (i + A[i] <= N) toact[i + A[i]].pb(i);
		if (i + B[i] + 1 <= N) todeact[i + B[i] + 1].pb(i);
	}
	for (int i = 1; i <= Q; i++) cout << out[i] << '\n';
}

Compilation message (stderr)

antennas.cpp:99:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   99 | main() {
      | ^~~~

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