Submission #1255262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255262		shafi_root	Two Antennas (JOI19_antennas)	C++20	100 / 100	463 ms	35952 KiB

antennas

/* _In The Name Of God_ */

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

#define maxs(a, b)			a = max(a, b)
#define mins(a, b)			a = min(a, b)
#define pb						push_back
#define F						first
#define S						second
#define lc						id << 1
#define rc						lc|1
#define mid						((l + r)/2)
// #define int                     long long

typedef pair<int, int>     	pii;
typedef long long               	ll;

const ll  MOD    = 1e9  + 7; // 998244353;
const ll  INF    = 1e9  + 1;
const int MXN    = 2e5  + 5;
const int LOG    = 23;

ll Pow(ll a, ll b) { return !b ? 1 : (Pow(a*a %MOD, b/2) * (b&1 ? a : 1)) %MOD; }

int n, h[MXN], q, ans[MXN], lz[2][MXN<<2];
pii L[MXN];
vector<pii> R[MXN], Q[MXN];

struct node {
	int mxl, ans;
} seg[2][MXN<<2];

void Build(int l = 0, int r = n + 1, int id = 1) {
	seg[0][id].mxl =
	seg[0][id].ans =
	seg[1][id].mxl =
	lz[0][id] = lz[1][id] =
	seg[1][id].ans = -INF;
	if (r - l < 2) {
		return;
	}
	Build(l, mid, lc);
	Build(mid, r, rc);
}

void Put(int op, int id, int x) {
	maxs(seg[op][id].ans, x + seg[op][id].mxl);
	maxs(lz[op][id], x);
}

void Shift(int op, int l, int r, int id) {
	if (r - l > 1 && lz[op][id] != -INF) {
		Put(op, rc, lz[op][id]);
		Put(op, lc, lz[op][id]);
		lz[op][id] = -INF;
	}
}

void Set(int op, int s, int x, int l = 0, int r = n+1, int id = 1) {
	Shift(op, l, r, id);
	if (r - l < 2) {
		seg[op][id].mxl = x;
		return;
	}
	if (s < mid) Set(op, s, x, l, mid, lc);
	else Set(op, s, x, mid, r, rc);
	seg[op][id].ans = max(seg[op][lc].ans, seg[op][rc].ans);
	seg[op][id].mxl = max(seg[op][lc].mxl, seg[op][rc].mxl);
}

void Upd(int op, int s, int e, int x, int l = 0, int r = n + 1, int id = 1) {
	Shift(op, l, r, id);
	if (s <= l && r <= e) {
		Put(op, id, x);
		return;
	}
	if (s < mid) Upd(op, s, e, x, l, mid, lc);
	if (mid < e) Upd(op, s, e, x, mid, r, rc);
	seg[op][id].ans = max({seg[op][lc].ans, seg[op][rc].ans});
}

int Get(int op, int s, int e, int l = 0, int r = n+1, int id = 1) {
	Shift(op, l, r, id);
	if (s <= l && r <= e) return seg[op][id].ans;
	if (e <= mid) return Get(op, s,e, l, mid, lc);
	if (mid <= s) return Get(op, s,e, mid, r, rc);
	return max({Get(op, s,e, l, mid, lc), Get(op, s,e, mid, r, rc)});
}

void _solve() {
    cin >> n;
	for (int i = 1; i <= n; i++) {
		int l, r;
		cin >> h[i] >> l >> r;
		L[i] = {max(0, i-r), max(0, i-l)};
		R[min(i+l, n+1)].pb({1, i});
		R[min(i+r+1, n+1)].pb({0, i});
	}
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;
		Q[r].pb({l, i});
	}
	// 0 : - +
	// 1 : + -
	fill(ans+1, ans +q + 1, -1);
	Build();
	for (int i = 1; i <= n; i++) {
		for (pii u : R[i]) {
			if (u.F) {
				Set(0, u.S, -h[u.S]);
				Set(1, u.S, h[u.S]);
			}
			else {
				Set(0, u.S, -INF);
				Set(1, u.S, -INF);
			}
		}
		Upd(0, L[i].F, L[i].S + 1, h[i]);
		Upd(1, L[i].F, L[i].S + 1, -h[i]);
		for (pii u : Q[i]) {
			maxs(ans[u.S], Get(0, u.F, i));
			maxs(ans[u.S], Get(1, u.F, i));
		}
	}
	for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int _ = 1;
    // cin >> _;
    while (_--) _solve();
    return 0.0;
}

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