Submission #960032

#	Time	Username	Problem	Language	Result	Execution time	Memory
960032		Pring	Two Antennas (JOI19_antennas)	C++17	100 / 100	510 ms	30544 KiB

antennas

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

const int MXN = 200005, INF = 1e9 + 39;
int n, q;

struct IN {
	int h, a, b;
} in[MXN];

struct QRY {
	int l, r, id;
} qry[MXN];

vector<pii> bck[MXN];
int ans[MXN];

struct LOSTONE {
#define mid ((l + r) >> 1)
#define ls id * 2 + 1
#define rs id * 2 + 2
	int val[MXN * 4], c[MXN * 4], tag[MXN * 4];
	void add_tag(int id, int l, int r, int _t) {
		val[id] = max(val[id], c[id] - _t);
		tag[id] = min(tag[id], _t);
	}
	void push(int id, int l, int r) {
		if (tag[id] == INF) return;
		add_tag(ls, l, mid, tag[id]);
		add_tag(rs, mid, r, tag[id]);
		tag[id] = INF;
	}
	void pull(int id, int l, int r) {
		c[id] = max(c[ls], c[rs]);
		val[id] = max(val[ls], val[rs]);
	}
	void init(int n) {
		fill(val, val + n * 4, -1);
		fill(tag, tag + n * 4, INF);
		fill(c, c + n * 4, -INF);
	}
	void grade(int id, int l, int r, int p, int _c) {
		if (l + 1 == r) {
			c[id] = _c;
			return;
		}
		push(id, l, r);
		if (p < mid) grade(ls, l, mid, p, _c);
		else grade(rs, mid, r, p, _c);
		pull(id, l, r);
	}
	void test(int id, int l, int r, int _l, int _r, int _h) {
		if (_l == _r) return;
		if (_r <= l || r <= _l) return;
		if (_l <= l && r <= _r) {
			add_tag(id, l, r, _h);
			return;
		}
		push(id, l, r);
		test(ls, l, mid, _l, _r, _h);
		test(rs, mid, r, _l, _r, _h);
		pull(id, l, r);
	}
	int query(int id, int l, int r, int _l, int _r) {
		if (_r <= l || r <= _l) return -1;
		if (_l <= l && r <= _r) return val[id];
		push(id, l, r);
		return max(query(ls, l, mid, _l, _r), query(rs, mid, r, _l, _r));
	}
#undef mid
#undef ls
#undef rs
} GOUKOKU;

void solve() {
	GOUKOKU.init(n);
#define abb(t, p) if (t <= n) bck[t].push_back(p)
	FOR(i, 0, n) {
		abb(i + in[i].a, mp(3, i));
		abb(i + in[i].b + 1, mp(3, -i - 1));
	}
	FOR(i, 0, q) {
		abb(qry[i].r, mp(2, i));
	}
#undef abb
	FOR(r, 0, n + 1) {
		for (auto [t, id] : bck[r]) {
			if (t == 3) {
				if (id >= 0) {
					GOUKOKU.grade(0, 0, n, id, in[id].h);
				} else {
					id = -id - 1;
					GOUKOKU.grade(0, 0, n, id, -INF);
				}
			} else {
				auto [l, _, aid] = qry[id];
				int x = GOUKOKU.query(0, 0, n, l, r);
				ans[aid] = max(ans[aid], x);
			}
		}
#define abb(x) max(0, x)
		if (r < n) {
			GOUKOKU.test(0, 0, n, abb(r - in[r].b), abb(r - in[r].a + 1), in[r].h);
		}
#undef abb
		bck[r].clear();
	}
}

void REVERSE() {
	reverse(in, in + n);
	FOR(i, 0, q) {
		qry[i].l = n - qry[i].l;
		qry[i].r = n - qry[i].r;
		swap(qry[i].l, qry[i].r);
	}
}

void miku() {
	cin >> n;
	FOR(i, 0, n) cin >> in[i].h >> in[i].a >> in[i].b;
	cin >> q;
	FOR(i, 0, q) {
		cin >> qry[i].l >> qry[i].r;
		qry[i].l--;
		qry[i].id = i;
	}
	fill(ans, ans + q, -1);
	solve();
	REVERSE();
	solve();
	FOR(i, 0, q) cout << ans[i] << '\n';
}

int32_t main() {
	cin.tie(0) -> sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	miku();
	return 0;
}

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