Submission #112591

#	Time	Username	Problem	Language	Result	Execution time	Memory
112591		KCSC	Two Antennas (JOI19_antennas)	C++14	100 / 100	1204 ms	39160 KiB

antennas

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

const int DIM = 200005;

const int INF = 1000000007;

int sgt1[DIM << 2], sgt2[DIM << 2], lzy[DIM << 2], ans[DIM];
vector<int> upd[DIM], lst[DIM];

struct Antenna {
	int h, a, b; } arr[DIM];

struct Query {
	int l, r; } qry[DIM];

void updateLazy(int nd, int le, int ri) {
	if (lzy[nd]) {
		sgt2[nd] = max(sgt2[nd], lzy[nd] - sgt1[nd]);
		if (le != ri) {
			lzy[nd << 1] = max(lzy[nd << 1], lzy[nd]);
			lzy[nd << 1 | 1] = max(lzy[nd << 1 | 1], lzy[nd]); }
		lzy[nd] = 0; } }

void build(int nd, int le, int ri) {	
	sgt1[nd] = INF; sgt2[nd] = -1; lzy[nd] = 0;
	if (le != ri) {
		int md = (le + ri) >> 1;
		build(nd << 1, le, md);
		build(nd << 1 | 1, md + 1, ri); } }

void update1(int nd, int le, int ri, int ps, int vl) {
	updateLazy(nd, le, ri);
	if (ri < ps or ps < le) {
		return; }
	if (le == ri) {
		sgt1[nd] = vl; }
	else {
		int md = (le + ri) >> 1;
		update1(nd << 1, le, md, ps, vl); 
		update1(nd << 1 | 1, md + 1, ri, ps, vl); 
		sgt1[nd] = min(sgt1[nd << 1], sgt1[nd << 1 | 1]); } }

void update2(int nd, int le, int ri, int st, int en, int vl) {
	updateLazy(nd, le, ri); 
	if (en < le or ri < st) {
		return; }
	if (st <= le and ri <= en) {
		lzy[nd] = max(lzy[nd], vl);
		updateLazy(nd, le, ri); }
	else {
		int md = (le + ri) >> 1;
		update2(nd << 1, le, md, st, en, vl); 
		update2(nd << 1 | 1, md + 1, ri, st, en, vl); 
		sgt2[nd] = max(sgt2[nd << 1], sgt2[nd << 1 | 1]); } } 

int query(int nd, int le, int ri, int st, int en) {
	updateLazy(nd, le, ri);
	if (en < le or ri < st) {
		return -1; }
	if (st <= le and ri <= en) {
		return sgt2[nd]; }
	else {
		int md = (le + ri) >> 1;
		return max(query(nd << 1, le, md, st, en),
							 query(nd << 1 | 1, md + 1, ri, st, en)); } }

int main(void) {
#ifdef HOME
	freopen("antennas.in", "r", stdin);
	freopen("antennas.out", "w", stdout);
#endif
	int N; cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> arr[i].h >> arr[i].a >> arr[i].b; }
	int Q; cin >> Q;
	for (int i = 1; i <= Q; ++i) {
		cin >> qry[i].l >> qry[i].r; ans[i] = -1; }
	for (int g = 1; g <= 2; ++g) {
		for (int i = 1; i <= N; ++i) {
			if (i + arr[i].a <= N) {
				upd[i + arr[i].a].push_back(i); }
			if (i + arr[i].b < N) {
				upd[i + arr[i].b + 1].push_back(-i); } }
		for (int i = 1; i <= Q; ++i) {
			lst[qry[i].r].push_back(i); }	
		build(1, 1, N);
		for (int i = 1; i <= N; ++i) {
			for (int x : upd[i]) {
				if (x > 0) {
					update1(1, 1, N, x, arr[x].h); }
				else {
					update1(1, 1, N, -x, INF); } }
			if (i - arr[i].a >= 1) {
				update2(1, 1, N, max(1, i - arr[i].b), i - arr[i].a, arr[i].h); }
			for (int x : lst[i]) {
				ans[x] = max(ans[x], query(1, 1, N, qry[x].l, qry[x].r)); } } 
		for (int i = 1; i <= N; ++i) {
			upd[i].clear(); lst[i].clear(); }
		for (int i = 1, j = N; i <= j; ++i, --j) {
			swap(arr[i], arr[j]); }
		for (int i = 1; i <= Q; ++i) {
			qry[i] = {N - qry[i].r + 1, N - qry[i].l + 1}; } }
	for (int i = 1; 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