Submission #458263

#	Time	Username	Problem	Language	Result	Execution time	Memory
458263		pavement	Two Antennas (JOI19_antennas)	C++17	0 / 100	382 ms	59736 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], out[200005];
vector<int> add[200005], del[200005];
vector<ii> qu[200005];

struct node {
	node *left, *right;
	int S, E, mx, mi, mxv, miv, val;
	bool ip;
	node(int _s, int _e) : S(_s), E(_e), val(-1e16), ip(0) {
		mx = mxv = -1e16;
		mi = miv = 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 || !ip) return;
		left->mxv = max(left->mxv, mxv);
		left->miv = min(left->miv, miv);
		right->mxv = max(right->mxv, mxv);
		right->miv = min(right->miv, miv);
		if (left->mi != 1e16 && left->miv != 1e16) left->val = max({left->val, llabs(left->mi - left->mxv), llabs(left->mx - left->miv)});
		if (right->mi != 1e16 && right->miv != 1e16) right->val = max({right->val, llabs(right->mi - right->mxv), llabs(right->mx - right->miv)});
		ip = 0;
		mxv = -1e16;
		miv = 1e16;
	}
	void set(int p) {
		if (S == E) {
			mx = mi = H[S];
			mxv = -1e16;
			miv = 1e16;
			return;
		}
		int M = (S + E) >> 1;
		prop();
		if (p <= M) left->set(p);
		else right->set(p);
		mx = max(left->mx, right->mx);
		mi = min(left->mi, right->mi);
		val = max(left->val, right->val);
	}
	void unset(int p) {
		if (S == E) {
			mx = mxv = -1e16;
			mi = miv = 1e16;
			return;
		}
		int M = (S + E) >> 1;
		prop();
		if (p <= M) left->unset(p);
		else right->unset(p);
		mx = max(left->mx, right->mx);
		mi = min(left->mi, right->mi);
		val = max(left->val, right->val);
	}
	void upd(int l, int r, int v) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			mxv = max(mxv, v);
			miv = min(miv, v);
			if (mi != 1e16) val = max({val, llabs(mi - mxv), llabs(mx - miv)});
			ip = 1;
			return;
		}
		prop();
		left->upd(l, r, v);
		right->upd(l, r, v);
		mx = max(left->mx, right->mx);
		mi = min(left->mi, right->mi);
		val = max(left->val, right->val);
	}
	int qry(int l, int r) {
		if (l > E || r < S) return -1e16;
		if (l <= S && E <= r) return val;
		prop();
		return max(left->qry(l, r), right->qry(l, r));
	}
} *root;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> 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);
	}
	root = new node(1, N);
	for (int i = 1; i <= N; i++) {
		for (auto j : del[i]) root->unset(j);
		for (auto j : add[i]) root->set(j);
		root->upd(max(1ll, i - B[i]), max(1ll, i - A[i]), H[i]);
		for (auto j : qu[i]) {
			out[j.second] = root->qry(j.first, i);
		}
		if (i + A[i] <= N) add[i + A[i]].pb(i);
		if (i + B[i] + 1 <= N) del[i + B[i] + 1].pb(i);
	}
	for (int i = 1; i <= Q; i++) cout << (out[i] == -1e16 ? -1 : out[i]) << '\n';
}

Compilation message (stderr)

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

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